10秒内计算出1亿素数表, 不输出

k9s

无心人#52的的程序，我改写了一下，基本上是一样的。gcc 编译1.6双核CPU 运行时间是>1000秒。 #include #include #include #define C17 510510 #define SIZE 255255 char BaseCache[SIZE],WorkCache[SIZE]; int PRIMES [43000]; int LOWSQRT, HIGHSQRT; //起始位置和结束位置的平方根 void initCache(void) { int p,i; for ( i = 0; i < SIZE ; i++ ) BaseCache[i] = 1; for ( p = 3; p <= 17; p+=2 ) { if ( p == 9 || p == 15 ) continue; for ( i = p >> 1; i < SIZE; i+=p ) BaseCache[i] = 0; } } void firstSieve(void) { int p,i,j,delta = 36,cigema = 180; for ( i = 0; i < SIZE; i++ ) WorkCache[i] = BaseCache[i]; LOWSQRT = (int)sqrt(C17-1); for ( p = 19; p <= LOWSQRT; p+=2 ) { if (WorkCache[p >> 1]) for ( j = cigema; j < SIZE; j+=p ) WorkCache[j] = 0; delta += 4; cigema += delta; } WorkCache[1] = 1; WorkCache[2] = 1; WorkCache[3] = 1; WorkCache[5] = 1; WorkCache[6] = 1; WorkCache[8] = 1; j = 1; PRIMES[j] = 2; for (i = 1; i < SIZE; i++) if (WorkCache[i]) PRIMES[++j] = (i << 1) + 1; PRIMES[0] = j; } void __fastcall nextSieve(int beg, int end) { int p,i,j,k; HIGHSQRT = (int)sqrt(end); for ( i = 0; i < SIZE; i++ ) WorkCache[i] = BaseCache[i]; 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[k] = 0; p = PRIMES[++i]; } while ( p <= HIGHSQRT ) { j = (p * p - beg + 1) >> 1; for ( k = j; k < SIZE; k+=p ) WorkCache[k] = 0; p = PRIMES[++i]; } LOWSQRT = HIGHSQRT; } int __fastcall PrimeCount(int len) { int c = 0,i; for ( i = 0; i < len; i++ ) if (WorkCache[i]) c++; return c; } int main() { int c,i,j,k; clock_t t1 = clock(),t2; initCache(); firstSieve(); c = PRIMES[0]; 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 ********************************************************************************************************/

k9s

//为什么您的程序只有500多毫秒，而我的却要1000多毫秒？ E:\worker>gcc -o shai shai.c -O3 E:\worker>shai --> time : 390 Prime Count: 5761455 不好意思，刚才忘了打-O3了哈哈！

无心人

呵呵 我的估计输在内存访问 用位数组，内存访问快

liangbch

同样是普通筛法，我的程序太慢了，没法和P1比阿。liangbch能发下你的p1源吗可以么？

62#的附件包含了多个算法的源代码，你可以下载下来看

无心人

liang什么时候回来阿

liangbch

按照这边给我定的日程表，八月底才能回来，时间太长了。 [ 本帖最后由 liangbch 于 2008-7-7 12:39 编辑 ]

无心人

哦 少了一份交流 呵呵 希望早点回来

gxqcn

原帖由 liangbch 于 2008-7-7 10:13 发表 按照这边给我定的日程表，八月底才能回不来，时间太长了。

应为：可能回不来？ 还是：才能回得来？ 确实：时间太长了。

tprime

看看附件这个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 [nr] [-n[nr]] [-s[s;u]] [-r[nr]] [-g[nr]] [-t[k]] [-p[k]] [-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

winxos

一下理解不了这么多， 以后慢慢来看， 以前自己写的筛法，用的是24的模的， 其他部分就跟死算一样， 慢的要死， 筛法确实是很讲究的东东， 期待新颖的素数判断法出现。