1

嘿伙计们，我正试图从我的发电机中挤出更多的质数，但在 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;
4

1 回答 1

9

除 2 和 3 外，所有素数都高于或低于 6 的倍数。这应该会将您的搜索空间减少到大约 1/3，而不是每次将 i 增加 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)
于 2013-05-10T18:12:28.377 回答