試圖解決沒有遞歸的最大素因子 - Ruby

我遇到了一個叫做歐拉項目的網站，一切都很順利，直到我遇到第三個問題 - 最大的主要因素。我不想用遞歸來解決它。我在網上看到他們使用Math.sqrt的解決方案，我也不想使用它。固執，我知道。試圖解決沒有遞歸的最大素因子 - Ruby

我想用循環和if語句解決它。我認爲輸入是一個奇數。這是我的代碼。如果num = 99，輸出保持爲[3]，我不知道爲什麼。我試圖在每個步驟都放置一個puts語句來查看輸出的內容。我意識到的一個問題是數組＃p在每個循環後都沒有重置。我嘗試了array.clear，但這並沒有多大幫助。有人能指出我正確的方向嗎？有沒有關於數組，循環和if語句的一些基本方面，我沒有得到？

def prime(num) 
    arr = [] 
    p = [] 
    not_p = [] 
    # first I find all the numbers that num is divisible by 
    for i in (2..num/2) 
     if num % i == 0 
      arr << i 
     end 
    end # this should output [3, 9, 11, 33] 

    arr.each do |x| # I loop through each element in the above array 
     for i in (2..(x/2)) # I divide each element - x - by 2 because it cannot be divisble by anything greater than its half 
      if x % i == 0 # if x is divisble by i 
       not_p << i # I push the i into array#not_p 
      end # keep looping until i reaches x/2 
     end 
     if not_p.length == 0 # if there are no values in array#not_p, then I know x is a prime factor 
      p << x # so I push x into array#p 
     end 
    end 
    return p[-1] # returns the last element of the array, which is the largest 
end 

puts prime(99)

來源

2015-01-13 user4318307

我不會給你完整的答案，因爲那樣會打敗Project Euler的做法。

但是，你幾乎是在正確的軌道上解決你的問題。你不想看看p沒有被清空，這應該是收集你的素數。儘管如此，你確實想看看not_p，因爲那是你每個因素的因數排列。

我希望這會有所幫助。讓我知道我是否可以再幫忙。

來源

2015-01-13 05:00:10 philnash

我仍然需要更多的幫助。在數組[3,9,11,33]中，99可以被整除，如果一個元素不能被任何數字整除到元素值的一半（因此對於9，任何數字從2〜4），我推該元素放入數組＃p中。如果它有因子，我將除數推入not_p。由於9確實有因子，因此數組＃not_p不爲空，因此9不會被壓入數組＃p。這是我的代碼背後的邏輯，但它不起作用。我的代碼究竟是不是在做我想要的事情呢？ – user4318307

這是正確的，但是你的問題在於，在你首先檢測到一個非素數，你的'not_p'數組中有項。因此，每當你再次圍繞循環'not_p.length'將不會再次爲零，除非你對此有所瞭解。 – philnash

明白了！感謝您的建議，並將我的解決方案添加到此主題中。 – user4318307

好的！感謝philnash的建議！事實上，我知道這個問題，並嘗試使用Array.clear清除數組，但這並不起作用。相反，我只是在迭代arr.each do | x |下面移動not_p = []它的工作！這是有道理的，因爲當它移動到下一個元素時，not_p會重置爲[]。非常感謝您的幫助，並且不會首先提供答案！這是我的最後，工作解決方案= D

def prime(num) 
    arr = [] 
    p = [] 

    for i in (2..num/2) 
     if num % i == 0 
      arr << i 
     end 
    end # this should output [3, 9, 11, 33] 

    arr.each do |x| 
     not_p = [] 
     for i in (2..(x/2)) 
      if x % i == 0 
       not_p << i 
      end 
     end 
     if not_p.length == 0 
      p << x 
     end 
    end 
    return p[-1] 
end 

puts prime(99) # => 29

來源

2015-01-13 20:21:28 user4318307

試圖解決沒有遞歸的最大素因子 - Ruby

回答

相關問題