项目欧拉＃3 - 寻找素因子

这是关于Project Euler问题3，如果你想尝试，因为它包含了答案它不预读！

所以，目标是要找到最大的主要因素为一些我写的代码做这个，但是当数字变到大，我不明白为什么，我想知道失败，如果有人能看看我。我能想到的唯一的事情是，这个数字对于某些PHP数据类型来说太大了？

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

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

它的工作原理，直到一个非常大的数字，即如果你13195测试你29作为国内最大的黄金，但如果你用600851475143（的问题）测试它给出了作为是不正确的最大素数。我知道答案是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>";

而且忽略过程中的文本位，我不能得到那个工作

来源

2013-04-04 ChrisBull

你的处理器或操作系统是32位的吗？ – 2013-04-04 20:01:25

nope，64.该死的最小字符数 – ChrisBull 2013-04-04 20:05:15

你的代码对我来说工作得很好。 – 2013-04-04 20:08:39

数600851475143是可以使用PHP整数，当你有一个32位的机器表示的范围之外，所以600851475143/6857不是整数：

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

你可以让你实现它的工作

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

在你的代码，这将是：：

整除与 bcmod从BC任意精度库检查

来源

2013-04-04 20:10:45 Joni

在控制面板>系统是说系统类型是64位 – ChrisBull 2013-04-04 20:37:52

也许你有一个32位版本的PHP，那么。在具有Linux'var_dump（600851475143/6857）'的64位机器上产生'int（87625999）'。 – Joni 2013-04-04 21:21:34

我怀疑你正在运行到整数溢出。目标号码600851475143被特别选择为不适合32位整数，所以这个问题可以作为其他需要大整数的问题的“门户”。解决方案是使用更大的数字数据类型。

来源

2013-04-04 20:09:17 user448810

在控制面板>系统是说系统类型x64 – ChrisBull 2013-04-04 20:37:33

也许PHP编译为32位。一个64位的操作系统将高兴地运行32位二进制文件。请转至http://php.net/manual/en/install.windows.manual.php并确保安装了64位二进制文件。

来源

2013-04-04 20:41:06

项目欧拉＃3 - 寻找素因子

回答

相关问题