算法 - 這個Erastothenes解決方案有什麼問題

我想我會創建自己的Sieve算法實現來更快地找到素數。令人驚訝的是，這沒有通過一些測試。算法 - 這個Erastothenes解決方案有什麼問題

這是我在Ruby中的算法，用於確定數字是否爲素數。

def prime?(n) 
    primes = [2,3,5,7,9,11,13,17] 
    primes.include?(n) || primes.none? { |p| n % p == 0 } 
end

算法如何工作是你把第一對夫婦的素數，我把前8個是安全的。然後，我會去除這些素數的所有倍數，因爲它們不可能是素數。

因此，所有其他的數字必須是素

我震驚地發現我的測試失敗，我忽略了一些數字。這怎麼可能？我完全遵循算法。

來源

2015-12-30 Richard Hamilton

任何不在您的有限列表中的質數產品將被您的函數錯誤地歸類爲質數。例如，19 * 19或19 * 23或19 * 29 * 37。 –

你沒有追隨Erastothenes的方法。 –

答案是你沒有完全遵循算法。而且，一旦你清除了前8個素數的所有倍數，所有其他數字都是素數，這是不正確的。 https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_and_varariants – jrochkind

測試給定數n你需要檢查它是否是整除的任何素數<的素性= sqrt（n）。既然你已經硬連線到17的素數，你的算法將只適用於值爲n < = 17 。

最重要的是，您在「素數」列表中包含了9個。這不應該影響你的測試，除了值9本身，因爲任何被9整除的東西也可以被3整除，但它很頑皮。

來源

2015-12-30 00:43:31 pjs

@CoderX我沒有發佈任何方法，我已經解釋了他的方法的侷限性。你不瞭解什麼部分的解釋？ – pjs

Erastothenes的方法不受限於<= 17 * 17。它只會找到下一個最小的數字，並刪除所有小於n的數字的倍數。 –

@CoderX他的實現受限於17 * 17。他可以測試素數的最大數量受限於他已知的最大素數的平方。 – pjs

首先，你已經在質數列表中包含了9個。 9不是素數。請嘗試以下方法。

查找所有數字以上的素數。從最小的素數開始，2.
標記2作爲素數，並刪除所有倍數2. 2.
接下來看哪個是最小的數字沒被刪除。它是3.打印3作爲素數，並刪除3的所有倍數小於n。

然後再選擇下一個最小的數不能刪除線了，等

def primeSeive(n) 
    while primes[index]**2 <= primes.last 
     prime = primes[index] 
     primes = primes.select { |x| x == prime || x%prime != 0 } 
     index += 1 
end

來源

2015-12-30 00:43:21

我不是很擅長ruby，但看起來你並沒有遵循這個算法。此外，你添加9作爲質數是不正確的。

篩算法首先只需要作爲素數。

僞：

Sieve(n) { 
    a[1] := 0       
    for i := 2 to n do a[i] := 1 
    p := 2 
    while p2 < n do { 
    j := p2 
    while (j < n) do {    
     a[j] := 0 
     j := j+p 
    } 
    repeat p := p+1 until a[p] = 1 
    } 
    return(a) 
}

這裏甲是陣列，其中的索引值指示primeness。 for not prime， for prime。在而循環標記素數倍數和最後挑選下一個素數重複部分。

來源

2015-12-30 05:31:20

算法 - 這個Erastothenes解決方案有什麼問題

回答

相關問題