發現的600851475143

Question

我試圖用一個程序來找到600851475143.最大的主要因素。這是項目歐拉這裏最大的主要因素：

： http://projecteuler.net/problem=3

我第一次使用此代碼嘗試這

#Ruby solution for http://projecteuler.net/problem=2 
    #Prepared by Richard Wilson (Senjai) 

    #We'll keep to our functional style of approaching these problems. 
    def gen_prime_factors(num) # generate the prime factors of num and return them in an array 
     result = [] 
     2.upto(num-1) do |i| #ASSUMPTION: num > 3 
     #test if num is evenly divisable by i, if so add it to the result. 
     result.push i if num % i == 0 
     puts "Prime factor found: #{i}" # get some status updates so we know there wasn't a crash 
     end 
     result #Implicit return 
    end 

#Print the largest prime factor of 600851475143. This will always be the last value in the array so: 
puts gen_prime_factors(600851475143).last #this might take a while 

這對於小數字來說很不錯，但是對於大數字來說，它需要很長的時間（以及大量的內存）。

不久前我就讀了大學微積分，但我很生疏，並沒有跟上我的數學。

我不想要一個直線上升的答案，但我想指出對資源或告訴我需要學習，以實現一些我在我的節目周圍可見的算法。

Answer 1

您的解決方案有幾個問題。首先，你永遠不會測試i是素數，所以你只能找到大數的最大因子，而不是最大的素數因子。您可以使用一個Ruby庫，只需require 'prime'，您可以將&& i.prime?添加到您的條件中。

這會解決誤差在你的程序，但它仍然是緩慢而昂貴的（事實上，現在會更貴）。你可以做的一件很明顯的事情就是設置result = i，而不是做result.push i，因爲你最終只關心你發現的最後一個可行的i，沒有理由保留所有主要因素的列表。

然而，即使如此，它仍然非常緩慢。正確的程序應該幾乎立即完成。關鍵是要縮小你正在測試的數量，每次你找到一個主要因素。如果你發現你的大數字的主要因素是p，那麼你不需要再一直測試到大數字。要測試到你的「新的」大數字是什麼將p出從大的數量中儘可能多地後左起：

big_number = big_number/p**n

其中n是最大的整數，右手方仍然是一個整數。在實踐中，你不需要明確地找到這個n，只是保持除以p，直到你停止獲得一個整數。

最後，作爲SPOILER我在下面提供了一個解決方案，但是如果您仍然想自己弄清楚，您可以選擇忽略它。

require 'prime' 

max = 600851475143; test = 3 

while (max >= test) do 
    if (test.prime? && (max % test == 0)) 
    best = test 
    max = max/test 
    else 
    test = test + 2 
    end 
end 

puts "Here's your number: #{best}" 

練習：證明test.prime?可以從if狀態被消除。 [提示：關於任何數字的最小（非1）除數，你能說什麼？]
練習：如果我們改用max = 600851475145，這個算法很慢。如何改進爲max的任何一個值？ [提示：手工找到600851475145的主分解;這很容易做到，它會說清楚爲什麼目前的算法很慢此號碼]