1

剧透

这是关于Project Euler的问题 3，如果您想尝试它，请不要提前阅读，因为它包含答案！

因此，目标是找到一个数字的最大素数，我编写的代码会这样做，但是当数字变大时会失败，我不知道为什么，我想知道是否有人可以帮我看看。我唯一能想到的是，对于某些 PHP 的数据类型来说，这个数字太大了？

我会粘贴我的代码，如果您没有本地测试环境，您可以将代码粘贴到这里，http://writecodeonline.com/php/

理论（我确信有更有效的方法来解决这个问题，但我既不是数学家也不是流利的编码器），它将从一个必须高于所有主要因素的数字开始，它然后依次尝试将起始数字除以另一个数字，如果结果是整数，它会一次又一次地运行该过程，直到它不再给出整数（必须是素数）。然后它将起始数字除以这个素数以获得一个新数字，然后将其插入第一个函数以获得一个新的素数和另一个数字，它一直这样做直到所有数字都是素数。然后是对最大素数的简单检查。

它一直有效，直到一个非常大的数字，即如果你测试13195你得到29最大的素数，但如果你用600851475143(The question) 测试它给出的最大素数是不正确的。我知道答案是6857，所以我确保我的起始计数器大于它，但它仍然失败 - 我不知道为什么。

感谢您的时间，这是代码（我再次知道会有更有效的方法，我想知道为什么我的方法不起作用）。

这是代码：

$startVal = 13195;
echo "<b>Starting Value</b> = $startVal<br /><br />";

$scriptTime = -microtime(true);

$testVar = 10000;
$primeArray = array();
$processArray = "";

function findPrimes($startStart,$startTest, array & $primeArray, $processArray) {
    $test = $startTest;
    $start = $startStart;
    $holdVal = NULL;
    for ($i=$test; $i > 1 ; $i--) { 
        if(is_int($start/$i) && $start != $i) {
            $processArray .= "$start is divisible by $i<br />";
            $start = $i;
            $i = $test +1;
        }
    }
    $processArray .= "Can't Divide Further<br /><b>Found a Prime : <font     color='red'>$start</font></b><br />";
    $primeArray[] = $start;
    if($start != $startStart) {
        $holdVal = $startStart/$start;
    }
    if(isset($holdVal)) {
        findPrimes($holdVal,$startTest,$primeArray,$processArray);
    }
    return array($primeArray,$processArray);
}

echo "Finding Primes...<br />";

$returnArray = findPrimes($startVal,$testVar,$primeArray,$processArray);
$primeArray = $returnArray[0];
$processArray = $returnArray[1];

echo "Script Found <b>".count($primeArray)."</b> Prime Numbers (";
for ($i=count($primeArray)-1; $i >= 0 ; $i--) {
    if(!$i == 0)
        echo $primeArray[$i].", ";
    else
        echo $primeArray[$i].")";
}
echo "<br />The largest Prime Factor of $startVal is <b><font     color='red'>".max($primeArray)."</font></b><br />";
$scriptTime = round(($scriptTime += microtime(true))* 1000, 3);
echo "<i>Script took $scriptTime milliseconds<br />";
echo "<br /><br /><b>Process</b><br />";
echo "<pre>";
print_r($processArray);
echo "</pre>";

也忽略进程文本位，我无法让它工作

4

3 回答 3

3

当您有一台 32 位机器时，数字 600851475143 超出了 PHP 中可以使用整数表示的范围，因此600851475143 / 6857不是整数：

php> var_dump(600851475143/6857);
float(87625999)

bcmod如果您使用BC 任意精度库实现可除性检查，则可以使其工作：

php> echo bcmod('600851475143','6857');
0

在您的代码中，这将是：

for ($i=$test; $i > 1 ; $i--) { 
    if(bcmod($start, $i) == 0 && $start != $i) {
        $processArray .= "$start is divisible by $i<br />";
        $start = $i;
        $i = $test +1;
    }
}
于 2013-04-04T20:10:45.773 回答
2

我怀疑你遇到了整数溢出。目标数字 600851475143 被特别选择为不适合 32 位整数，因此这个问题充当了其他同样需要大整数的问题的“网关”。解决方案是使用更大的数字数据类型。

于 2013-04-04T20:09:17.307 回答
1

也许 PHP 是为 32 位编译的。64 位操作系统将愉快地运行 32 位二进制文​​件。转到http://php.net/manual/en/install.windows.manual.php并确保您已安装 64 位二进制文​​件。

于 2013-04-04T20:41:06.557 回答