PHP更快的素数生成器

Question

嘿伙计们,我正试图从我的发电机中挤出更多的质数,但是在第60次运行中已达到+ - 14,000,000左右的极限值,我希望尽可能推高可能达到25-30万.关于如何完成这一壮举的任何想法？

这是我的PHP代码

<?php
$i = 2;
$primes = array();
while(true)
{
    $prime=true;
    $sqrt=floor(sqrt($i));
    foreach($primes as $num)
    {
        if($i%$num==0)
        {
            $prime=false;
            break;
        }
        if($num>$sqrt) break;
    }
    if($prime) echo "$i\n";
    $i++;
}

这是运行它的小bash脚本

#!/bin/bash
outfile="$1.out"
`php $1 > $outfile &`
sleep 60
killall php

编辑

这是昨晚的pcntl_forked版本只是为了看看会更快.出于一些奇怪的原因,我做得越少越好,如果是,我发现瓶颈来自gmp_strval(gmp_nextprime($start))哪个非常慢.

<?php
$primeCount = 0;
for ($i = 1; $i <= 1; ++$i) {
    $start = $i;
    $pid = pcntl_fork();

    if (!$pid) {
        while(true) echo $start = gmp_strval(gmp_nextprime($start)) . "\n";
        exit($i);
    }
}

while (pcntl_waitpid(0, $status) != -1) {
    $status = pcntl_wexitstatus($status);
    #echo "Child $status , $primeCount completed\n";
}
die;

Answer 1

除了2和3之外,所有素数都是高于6的倍数或者低于6的倍数.这应该将您的搜索空间减少到大约1/3而不是每次递增1.用2,3筛选筛子并使用缩小的搜索空间来加快时间.

如果您需要一个简单的解释:

1 + n*6 (This is one above, and I state it's got primes)
2 + n*6 (multiple of 2)
3 + n*6 (multiple of 3)
4 + n*6 (multiple of 2)
5 + n*6 (This is one below, and I state it's got primes)
6 + n*6 (multiple of 2,3,6)