我的函數尋找最高素數因子有什麼問題？

function find_highest_prime_factor($n) 
{ 
    for ($i = 2; $i <= $n; $i++) 
    { 
     if (bcmod($n, $i) == 0) //its a factor 
     { 
      return max($i, find_highest_prime_factor(bcdiv($n,$i))); 
     } 
    } 
    if ($i == $n) 
    { 
     return $n; //it's prime if it made it through that loop 
    } 
}

UPDATE：這是正確的答案，我的不好！我的函數尋找最高素數因子有什麼問題？

來源

2011-08-18 babonk

你能舉一個例子輸入嗎？ – webbiedave

如果'（$ i == $ n）'是多餘的，它總是如此。 –

擺脫最終的if語句，否則如果$i!=sqrt($n)因爲開方（$ n）是不是你有一個未定義的返回值

function find_highest_prime_factor($n){ 
    for ($i = 2; $i <= sqrt($n); $i++) //sqrt(n) is the upperbound 
    { 
     if (bcmod($n, $i) == 0) //its a factor 
     { 
      return max($i, find_highest_prime_factor(bcdiv($n,$i))); 
     } 
    } 
    return $n; //it's prime if it made it through that loop 
}

來源

2011-08-19 00:14:44

仍然沒有得到儘管最高素數..似乎沒有在與我正在做的那個答案中有所作爲 – babonk

這甚至更好：如果它通過第一個循環，它必須是素數，不需要再次測試。 ... – Jonah

你試過哪個答案，因爲這個版本修正了錯誤14 –

11號線應該是：

if ($i == ceil(sqrt($n)))

來源

2011-08-19 00:02:26 Jonah

你的sqrt優化是好的，我的最初答覆是錯誤的。回到你原來的代碼並做出上面的改變，一切都會很好。鏈接到OP的原始代碼，與我的更改：http://codepad.viper-7.com/1aODAo – Jonah

此更改似乎不起作用：http://codepad.viper-7.com/C84m7z – babonk

啓動整數在2並且步進1是低效的。至少分別檢查2，然後每次從3步2循環。使用2-4輪會更快。

當您遞迴代碼時，再次以試用因子2開始。最好傳遞第二個參數，以保存迄今已達到的因子。然後遞歸不會回溯到已經測試過的舊因素。

來源

2011-08-19 12:23:31 rossum

我的函數尋找最高素數因子有什麼問題？

回答

相關問題