欧拉计划#3-寻找主要因素 [英] Project Euler #3 - Finding Prime Factors

问题描述

SPOILER

这与 Project Euler 上的问题3有关，如果您想尝试使用该问题，请不要先阅读，因为它包含答案！

This is about question 3 on Project Euler if you want to try it do not read ahead as it contains the answer!

所以目标是找到一个我写的代码可以做到的最大素数，但是当这个数字变大而我无法弄清楚为什么的时候失败，我想知道是否有人可以找一个我.我唯一能想到的是，对于某些PHP的数据类型而言，这个数字太大了吗?

So the objective is to find the largest prime factor for a number the code I have written does this but fails when the number gets to big and I can't work out why, I was wondering if someone could take a look for me. The only thing I can think of is that the number is too large for some of PHP's data types?

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

I will paste my code, if you don't have a local test environment you can paste the code onto here, http://writecodeonline.com/php/

理论(我相信有很多更有效的方法可以解决这个问题，但是我既不是数学家，也不是流利的编码器)，它的起点是一个必须高于所有素数的数字因数，然后依次尝试将起始数除以另一个数，如果结果是整数，它将一次又一次地运行该过程，直到不再提供整数(必须是质数).然后，它将起始数字除以该质数因子得到一个新数，然后将其插入第一个函数中以获取一个新质数和另一个数，它一直这样做直到所有的质数都是质数.然后有一个简单的检查最大素数.

The theory (I'm sure there are much more efficient ways to solve this but I'm neither a mathematician nor a fluent coder), is that it will start at a number which has to be higher than all of the prime factors, it then sequentially tried to divide the starting number by another number, if the result is an integer it runs the process again and again until it no longer gives an integer (must be a prime factor). It then divides the starting number by this prime factor to get a new number which it then plugs back into the first function to get a new prime number and another number, it keeps doing this until all numbers are prime. Then there is a simple check for the largest prime.

它可以工作到非常大的数字，即，如果使用13195进行测试，则会得到29作为最大质数，但是如果使用600851475143进行测试(问题)，它将给出为最大质数，即不对.我知道答案是6857，所以我确保我的起始计数器大于它，但仍然失败-我无法弄清楚为什么.

It works up until a very large number, i.e if you test with 13195 you get 29 as the largest prime but if you test with 600851475143 (The question) it gives that as the largest prime which isn't right. I know that the answer is 6857 so I make sure that my starting counter is larger than it but it still fails - I can't work out why.

感谢您的时间，这是代码(同样，我知道会有更有效的方法，我想知道为什么我的方法不起作用).

Thanks for your time, here is the code (again I know there will be more efficient methods, I would like to know why mine doesn't work).

代码如下:

$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>";

也忽略了过程文本位，我无法正常工作

Also ignore the process text bit, I can't get that to work

推荐答案

当您拥有32位计算机时，数字600851475143超出了可以在PHP中使用整数表示的范围，因此600851475143 / 6857不是整数:

The number 600851475143 is outside of the range that can be represented using integers in PHP when you have a 32bit machine, so 600851475143 / 6857 is not an integer:

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

如果使用 bcmod 来自BC任意精度库:

You can make it work if you implement the divisibility check with bcmod from the BC arbitrary precision library:

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;
    }
}

这篇关于欧拉计划#3-寻找主要因素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！