項目歐拉＃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 - 尋找素因子

回答

相關問題