php - 主发电机优化

我正在开始我的欧拉计划探险。和其他许多我已经想到的一样，我需要制作一个质数生成器。问题是：PHP不喜欢大数字。如果我使用标准的Sieve of Eratosthenes function，并将限制设置为200万，它将崩溃。它不喜欢创建该大小的数组。可以理解的

所以现在我正在尝试对其进行优化。我发现，一种方法是创建一个带有200万个变量的数组，而不是只需要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），我终于设法得到了答案。 je

最佳答案

来自Algorithmist's proposed solution


这是对标准的修改
Eratosthenes筛。这将是
效率很低，也用光了很多
大量的内存和时间来运行
标准筛一直到n。
但是，不小于
等于n将有一个因数
大于sqrt {n}，
所以我们只需要知道所有的素数
到这个极限，不大于
比31622（10 ^ 9的平方根）。这个
用筛子完成。然后，
对于每个查询，我们仅筛选
给定的范围，使用我们的
预先计算的素数表
消除复合数字。


这个问题也出现在UVA和Sphere的在线评审中。 Here's how it's enunciated on Sphere.