我正在嘗試在Ruby 2.1中實現this "find the nth prime number" algorithm。這個天真的素數算法爲什麼會失敗？

我已經標記了'算法'，因爲我認爲這個問題是語言不可知的，而且即使你不熟悉，所寫的Ruby代碼也足夠簡單。我使用了描述性變量名稱來幫助它。

遍歷整個數字系統，忽略甚至大於號碼2（2，3，5，7，...）
對於每個整數，p，檢查如果p是素數：
1. 迭代對於已發現的素數小於p的平方根
2. 對於這個集合中的每個素數f，檢查它是否是p的因子： i。如果f除p，那麼p是非素數。從2繼續下一頁。
3. 如果找不到任何因素，p就是素數。繼續3.
如果p不是我們找到的第n個素數，請將其添加到素數列表中。從2繼續下一頁。
否則，p是我們找到的第n個素數，我們應該返回它。

聽起來很簡單。所以我寫我的方法（函數）：

def nth_prime(n) 
     primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] 

     primes[-1].upto(Float::INFINITY) do |p| 
      return primes[n-1] if primes.length >= n-1 
      possible_prime = true 
      primes_to_check = primes.select{|x|x<=Math.sqrt(p)} 
      primes_to_check.each do |f| 
       if f%p==0 
        possible_prime = false 
        break 
       end 
      end 
      primes << p if possible_prime 
     end 
    end

意圖是說nth_prime(10)並得到第10個素數。

解釋我的邏輯：

我開始已知質數列表，因爲算法要求。我列出前十名。

然後我遍歷整個數字系統。 (primes[-1]+2).upto(Float::Infinity) do |p|將提供從最後一個已知素數加上兩個數字（因爲+1將導致偶數並且均勻超過2不能爲素數），以無限於p的縮進塊。我沒有跳過偶數和有

我做的第一件事就是返回ñ個質數，如果已知素數的名單已經至少ň元素長。這對於已知的值是有效的 - 如果你問5號，你將得到11。

然後我將一個標誌possible_prime設置爲true。這表明沒有任何證據證明它是而不是。我要做一些測試，如果它沒有改變爲false，那麼p被證明是質數，並被附加到已知質數陣列。最終該陣列將長達n並返回第n個值。

我創建了一個數組，primes_to_check，包含所有已知的素數< = p的平方根。每個人依次被測試爲f。

若f可以清晰地劃分p，我知道，p是不是素數，所以我改變標誌false，並且break，這給我們帶來了素數對循環校驗和回到upto-無限循環。在該循環中只剩下一條語句，即如果該標誌爲真，則追加到已知素數數組中的語句，這不是我們重新啓動具有下一個數字的循環。

如果沒有f S能幹淨利落地劃分p那麼p必須是素的，這意味着它生存的素數 - 校驗循環使用仍設置爲true的結束標誌，並達到最終的「追加p到已知素數的聲明。

最終這將使primes數組足夠長以回答「什麼是第n個素數？」這個問題。

問題

問計於10日黃金確實讓我29，上次主我預先提供的。但要求11獲得nil，或沒有價值。我已經完成了上百次代碼，無法想象沒有返回值的情況。

我做錯了什麼？

來源

2015-04-04 GreenTriangle

return primes[n-1] if primes.length >= n-1

對於primes到具有索引n-1的元素，它的長度必須至少n。

if f%p==0

這檢查一個已知的素數是否可以被候選人整除，而不是候選人是否可以被已知的素數整除。

primes[-1].upto(Float::INFINITY) do |p|

這開始在列表（29）中已經存在的主要循環。 29被正確地認定爲素數，所以它又被添加到列表中。你需要在29之後開始循環。

來源

2015-04-04 07:33:05 user2357112

嗯。良好的發現，我想我正在考慮零索引或那裏的東西。但將它改爲'n'而不是'n-1'會引入一個新的錯誤：第11個素數返回第10個，並且每個附加數字只返回下一個整數，而不是下一個素數。 – GreenTriangle 2015-04-04 08:14:16

@GreenTriangle：發現更多的錯誤。如果還有更多，請在再次詢問之前嘗試自己找到它們。 – user2357112 2015-04-04 08:25:07

Algorithm for testing prime no.s: 
1)Input num 
2)counter= n-1 
3)repeat 
4)remainder = num%counter 
5)if rem=0 then 
6)broadcast not a prime.no and stop 
7)change counter by -1 
8)until counter = 1 
9)say its a prime and stop

來源

2016-10-05 20:29:00

這個回答怎麼樣？我做了什麼錯了？'？這是否找到第n個素數？就像從2開始並且向上一樣有效嗎？ – greybeard 2016-10-05 21:25:34

是的，當你輸入一個數字時，它會告訴你它是否是素數。 – 2016-10-06 14:59:42

第n個素數是別的：如果你輸入5，你不應該回答真（或假），2,3,5,7或9，而是'11'，因爲它是第五個質數。（無論如何，GreenTriangle的問題仍然是「我做錯了什麼？」） – greybeard 2016-10-06 16:19:01

這個天真的素數算法爲什麼會失敗？

問題

回答

相關問題