#include <stdio.h>
#include <math.h>
#include <time.h>
#define C17 510510
#define SIZE 255255
char BaseCache,WorkCache;
int PRIMES ;
int LOWSQRT, HIGHSQRT; //起始位置和结束位置的平方根
void initCache(void)
{
int p,i;
for ( i = 0; i < SIZE ; i++ )
BaseCache = 1;
for ( p = 3; p <= 17; p+=2 )
{
if ( p == 9 || p == 15 )
continue;
for ( i = p >> 1; i < SIZE; i+=p )
BaseCache = 0;
}
}
void firstSieve(void)
{
int p,i,j,delta = 36,cigema = 180;
for ( i = 0; i < SIZE; i++ )
WorkCache = BaseCache;
LOWSQRT = (int)sqrt(C17-1);
for ( p = 19; p <= LOWSQRT; p+=2 )
{
if (WorkCache)
for ( j = cigema; j < SIZE; j+=p )
WorkCache = 0;
delta += 4;
cigema += delta;
}
WorkCache = 1;
WorkCache = 1;
WorkCache = 1;
WorkCache = 1;
WorkCache = 1;
WorkCache = 1;
j = 1; PRIMES = 2;
for (i = 1; i < SIZE; i++)
if (WorkCache)
PRIMES[++j] = (i << 1) + 1;
PRIMES = j;
}
void __fastcall nextSieve(int beg, int end)
{
int p,i,j,k;
HIGHSQRT = (int)sqrt(end);
for ( i = 0; i < SIZE; i++ )
WorkCache = BaseCache;
i = 8; p = 19;
while ( p <= LOWSQRT )
{
j = beg % p;
if (j != 0)
{
j = beg + p - j;
if (j % 2 == 0) j+=p;
} else j = beg;
j = (j - beg + 1) >> 1;
for ( k = j; k < SIZE; k+=p )
WorkCache = 0;
p = PRIMES[++i];
}
while ( p <= HIGHSQRT )
{
j = (p * p - beg + 1) >> 1;
for ( k = j; k < SIZE; k+=p )
WorkCache = 0;
p = PRIMES[++i];
}
LOWSQRT = HIGHSQRT;
}
int __fastcall PrimeCount(int len)
{
int c = 0,i;
for ( i = 0; i < len; i++ )
if (WorkCache) c++;
return c;
}
int main()
{
int c,i,j,k;
clock_t t1 = clock(),t2;
initCache();
firstSieve();
c = PRIMES;
int beg = C17 + 1,end = (C17 << 1) - 1;
while ( end < 100000000 )
{
nextSieve(beg,end);
c += PrimeCount(SIZE);
beg += C17; end += C17;
}
end = 99999999;
nextSieve(beg,end);
c += PrimeCount((end - beg)>>1);
t2 = clock();
printf("--> time : %d\n",t2-t1);
printf("Prime Count: %d\n",c);
return 0;
}
/********************************************************************************************************
--> time : 1023
Prime Count: 5761455
********************************************************************************************************/ //为什么您的程序只有500多毫秒，而我的却要1000多毫秒？
E:\worker>gcc -o shai shai.c -O3
E:\worker>shai
--> time : 390
Prime Count: 5761455
不好意思，刚才忘了打-O3了哈哈！:lol 呵呵
我的估计输在内存访问
用位数组，内存访问快 同样是普通筛法，我的程序太慢了，没法和P1比阿。liangbch能发下你的p1源吗可以么？
62#的附件包含了多个算法的源代码，你可以下载下来看 liang什么时候回来阿 按照这边给我定的日程表，八月底才能回来，时间太长了。
[ 本帖最后由 liangbch 于 2008-7-7 12:39 编辑 ] :)
哦
少了一份交流
呵呵
希望早点回来 原帖由 liangbch 于 2008-7-7 10:13 发表 http://bbs.emath.ac.cn/images/common/back.gif
按照这边给我定的日程表，八月底才能回不来，时间太长了。
应为：可能回不来？
还是：才能回得来？
确实：时间太长了。:D 看看附件这个ecprime的威力吧
100亿的筛法只要4s(AMD 3600+ 单线程)
还能计算素数间距, K生素数等(这个不如我的程序)
有时间我将它改成多进程的,
四核机器百亿只要1s
以下是作者的help
23.10.2003, e0325944@student.tuwien.ac.at
help file, ecprime 1.4 by Kim Walisch
#--------------------------------------------------
version 1.4, 2003
ecprime [-n] [-s] [-r] [-g] [-t] [-p] [-c] [-d]
#--------------------------------------------------
Usage:
# Count Functions
ecprime 1000
counts primes (0 - 1000)
ecprime 1000 -n100
counts primes (100 - 1000)
ecprime 1000 -n100 -t2
counts 2-tuplets (100 - 1000)
i.e -t3,-t4,-t5,-t6,-t7
# Print Functions
ecprime 1000 -p1
prints primes (0 - 1000) to primes.txt
ecprime 1000 -p2
prints 2-tuplets (0 - 1000) to 2-tuplets.txt
i.e -p3,-p4,-p5,-p6,-p7
# Settings
ecprime 1000 -s3
uses a sieve of 2^3KB, -s(0 - 24)
max speed for sieve = L1-cache
ecprime 1000 -s7;4
uses a sieve of 2^7 KB, divided into subsieves of 2^4 KB, fast for numbers > 10^12
ecprime 1000 -r17
uses a repetion field of 17#/30 bytes, -r(7 - 23)
see limits file for details
# Detailed Time Output, -d
time1: initialization repetition field
time2: initialization small primes
time3: sieving time (std)
# Prime Gaps
ecprime 1000 -g
prints first occurrence gaps to gaps.txt
ecprime 1000 -g100
prints first occurrence gaps (>100) to gaps.txt
ecprime 1000 -g100 -c
prints all prime gaps (>100) to gaps.txt
收藏
一下理解不了这么多，以后慢慢来看，
以前自己写的筛法，用的是24的模的，
其他部分就跟死算一样，
慢的要死，
筛法确实是很讲究的东东，
期待新颖的素数判断法出现。