如何在PHP中用不到1分钟的时间计算0到100000000之间的素数？
请帮我计算介于0到100000000之间的素数因为我用来写但它的工作速度很慢：
这是我的代码：
$n =100000000; $answer =0; for ($i = 2, $j = 2; $i <= $n; $i++) { for ($j = 2; $j < $i; $j++) { if ($i % $j == 0) { break; } } if ($j == $i) { $answer++; } } echo $answer . PHP_EOL; 看看Eratosthenes的Sieve 。 在现代桌面上，这个问题可以在不到2秒的时间内解决。 您还可以尝试在内存和速度方面表现更好的Bitwise Sieve 。
如前所述，使用Eratosthenes的Sieve
- 在我的AMD 3.2 GHz Win7 x64单线程32位C ++（BDS2006）应用程序：
-
[4929.114 ms] find primes <= 100000000 found 5761456 primes - 所以花了将近5秒的时间来计算
- 我的实现使用任何奇数的单位，所以你需要N / 16字节的内存
- 对于你的10亿，它几乎是6 MB，我认为这是好的
这是C ++中的源代码：
//--------------------------------------------------------------------------- int primes_found=0; void addprime(int p) { // here do the stuff you want to do with prime p=2,3,5,7,... // I just count the primes found ... primes_found++; } //--------------------------------------------------------------------------- void getprimes(int p) // compute all primes up to p { // sieves N/16 bytes // ------------------------------ // 0 1 2 3 4 5 6 7 bit // ------------------------------ // 1 3 5 7 9 11 13 15 +-> +2 // 17 19 21 23 25 27 29 31 | // 33 35 37 39 41 43 45 47 V +16 // ------------------------------ int N=(p|15),M=(N>>4)+1; // store only odd values 1,3,5,7,... each bit ... char *m=new char[M]; // m[i] -> is 1+i+i prime? (factors map) int i,j,k; // init sieves m[0]=254; for (i=1;i>4]&=255-(1<<((j>>1)&7)); // compute primes addprime(2); for(i=1,j=i>>4;j
- 你可以使用
#define addprime(prime) {...}代替函数 - 但在我的编译器中有点慢（不知道为什么）
用法：
getprimes(100000000);
[笔记]
- 即使这可以进一步优化和加速（初始筛子部分）
- 但我懒得去尝试
- 这在我的设置上更快，然后N / 2字节版本可能是由于缓存
[edit1] init仅通过素数进行筛选
// init sieves m[0]=254; for (i=1;i>4]; if (int(a& 1)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2; if (int(a& 2)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2; if (int(a& 4)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2; if (int(a& 8)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2; if (int(a& 16)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2; if (int(a& 32)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2; if (int(a& 64)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2; if (int(a&128)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2; }
-
[1520.160 ms] find primes <= 100000000 found 5761456 primes - 现在需要约1.5秒
- 我检查了第一个1000000素数（最多15485863），输出正确
更改算法。 使用欧拉筛。
这是我的C ++代码。 它只需3或4秒。
bool isprm[100000000+10]; int prm[5000000]; clr(isprm, true); int cnt = 0; for(int i=2; i<=n; i++) { if(isprm[i]) prm[++cnt] = i; for(int j=1; j<=cnt && LL(i)*prm[j]<=n; j++) { isprm[ i*prm[j] ] = false; if(i % prm[j] == 0) break; } }
跳过偶数大2并停在我的平方根应该加快速度
我的代码：
int max = 100000000; int i, j; int answer = 0; for(i=2;i= i) answer++; }