我开始进行欧拉计划的远足。和许多其他人一样，我发现需要生成质数。问题是：PHP不喜欢大数字。如果我使用标准的埃拉托色尼筛法函数，并将限制设置为200万，它会崩溃。它不喜欢创建那么大的数组，这是可以理解的。
所以现在我正在尝试优化它。我找到的一个方法是，不再创建一个有两百万个变量的数组，而只需要100万个（因为只有奇数才可能是质数）。但现在它因超出最大执行时间而崩溃...
所以现在我正在尝试优化它。我找到的一个方法是，不再创建一个有两百万个变量的数组，而只需要100万个（因为只有奇数才可能是质数）。但现在它因超出最大执行时间而崩溃...
function getPrimes($limit) {
$count = 0;
for ($i = 3; $i < $limit; $i += 2) {
$primes[$count++] = $i;
}
for ($n = 3; $n < $limit; $n += 2) {
//array will be half the size of $limit
for ($i = 1; $i < $limit/2; $i++) {
if ($primes[$i] % $n === 0 && $primes[$i] !== $n) {
$primes[$i] = 0;
}
}
}
return $primes;
}
这个函数可以正常工作，但是有点慢...你有什么建议吗？
我发现一个方法可以让它变得更快，就是改变循环的顺序。
foreach ($primes as $value) {
//$limitSq is the sqrt of the limit, as that is as high as I have to go
for ($n = 3; $n = $limitSq; $n += 2) {
if ($value !== $n && $value % $n === 0) {
$primes[$count] = 0;
$n = $limitSq; //breaking the inner loop
}
}
$count++;
}
除了设置时间和内存限制（感谢Greg），我终于成功得到了答案。phjew。