試圖尋找最大素因子

問題的第三個問題：的13195的首要因素是5，7，13和29 什麼數字600851475143的最大素數？

因爲這是一個難題，所以我不想使用罐裝Ruby方法。所以這裏...

當前邏輯：
num是我們正在尋找的主要因素的數量。
候選人是一個潛在的主要因素
開方是NUM的平方根

until candidate >= sqrt

我借用了埃拉托色尼的篩這個想法尋找素數，其中算法檢查每一個數字整除達廣場數量的根。候選者是要測試的數字，如果num有除數。

if num % candidate == 0 
... 
end

目標是檢查num是否可以被任何事物（有因素）整除。如果num無法被候選人整除，則候選人將遞增1，直到until聲明爲真，或者直到num被候選人整除。

如果num可以被候選人整除，那麼我們知道候選人是素數，並且它被插入prime_factor中。然後遞歸發生測試新定義的數字。

prime_factors << num

如果until循環是真的，那NUM沒有除數，因此是素數。結果，它被插入到prime_factors中。

問題：

的問題不在於它的超時而在於它給了錯誤的答案。看起來，我的代碼循環超過需要。我添加了一些日誌記錄。我不知道爲什麼，但我認爲它與遞歸片斷有關。無可否認，我從來沒有在我的代碼中使用遞歸，而是想用它來擴展我的技能。所以從概念上講，遞歸總的來說是模糊的。任何閱讀都會有幫助。

應該發生什麼：
prime_factors = [2,2,19]
prime_factors.last = 19

什麼實際發生的情況：
prime_factors = [2,2,19,19,38]
prime_factors.last = 38

整個代碼：

def largest_prime_factor(num,prime_factors) 
puts "beg fx: num: #{num}, prime_factors: #{prime_factors} 
candidate = 2 
sqrt = Math.sqrt(num) 
loop_count = 0 
until candidate >= sqrt 
    if num % candidate == 0 
    num = num/candidate 
    prime_factors << candidate 
    largest_prime_factor(num,prime_factors) 
    end 
    candidate += 1 
    loop_count +=1 
end 
    puts "outside loop: candidate >= sqrt is #{candidate >= sqrt} num: #{num}, prime_factors: #{prime_factors}, candidate: #{candidate}, sqrt: #{sqrt}, loop: #{loop_count}" 
    gets 
prime_factors << num 
prime_factors.last 
end

來源

2016-02-23 dstrube

順便提一句'require'prime'; Prime.prime_division（76）[ - 1] [0]' – Amadan

你永遠不會檢查你追加到prime_factors的數字實際上是質數 –

如果發佈你在這種情況下跟隨的算法會更容易。從另一個類似主題的問題，我明白這是一個項目歐拉問題，所以可以有很多方法來解決。既然你打算弄清楚你的代碼有問題，那麼最好在算法中加入算法。 – Kashyap

所以看起來升正如你所建議的那樣，問題在於遞歸邏輯。

僅僅因爲你遞歸調用函數並不意味着「父」停止工作 - 他只是坐着等待「小孩」完成，然後繼續前進。這就是發生這種「過度循環」的地方。代碼實際上不是循環，而是完成。

你可以在你的puts語句中看到這個。請注意，循環停止後，sqrt會增加，因爲腳本現在正在運行父代碼，而不是遞歸部分（子代）完成後。

對於修復，我做了兩件事： 1.創建一個布爾值，指示代碼塊已經通過遞歸。如果是這樣，運行這個代碼，否則...運行其他的東西。 2.如果候選人不是2，則增加2.這將跳過除2之外的所有偶數測試。不需要測試其他偶數，因爲它不是素數。

def largest_prime_factor(num,prime_factors,recursive) 
    candidate = 2 
    until candidate >= Math.sqrt(num) 
    recursive = false 
    if num % candidate == 0 
     num = num/candidate 
     recursive = true 
     prime_factors << candidate 
     largest_prime_factor(num,prime_factors,recursive) 
    end 
    break if recursive 
    candidate == 2 ? candidate += 1 : candidate += 2 
    end 
    prime_factors << num unless recursive 
    prime_factors.last 
end

來源

2016-02-24 21:07:03

試圖尋找最大素因子

回答

相關問題