搜索特定數字的大數字列表的效率

我有以下代碼，其中eratosthenes(N)返回從1到N的素數數組。我想要做的是從此列表中刪除包含數字0,2的任何數字，4，5，6，8。我的代碼看起來效率很低並且錯誤，因爲它需要大約20秒（eratosthenes(N)是瞬時的）才能達到10萬，並且不會刪除我想要的所有數字。是否有更好的，可擴展的解決方案來解決這個問題？搜索特定數字的大數字列表的效率

N = 1_000_000 
primes = eratosthenes(N) 

primes.each do |num| 
    if ["0", "2", "4", "5", "6", "8"].any? { |digit| num.to_s.include?(digit) } 
     primes.delete(num) 
    end 
end

來源

2016-08-31 Ciaran S

「含有數字0，2，4，5，6，8」 - 我敢肯定這是AW rong方法來提高Eratosthenes的篩選效率。你想跳過_last_數字就是其中之一的數字，不是嗎？ –

另外，不要改變你當前正在迭代的數組。這應該解釋爲「不會刪除我想要的所有數字」 –

刪除0,2,4,5,6,8的原因與我最初搜索素數時分開。我已經有了我的素數組，我想進一步挑選。第二點是適當注意的。 –

與方法的問題是，每個delete重寫數組，這就是所謂的每一個刪除的項目，所以複雜性的算法是O（n^2）而不是O（n）。

你應該做這樣的事情：

primes.reject!{|num| ["0", "2", "4", "5", "6", "8"].any? { |digit| num.to_s.include?(digit) }}

或者乾脆：

primes.reject!{|num| num.to_s[/[024568]/]}

這只是一個風格問題，但我會在一條線連起來（注意缺乏!在這裏reject）：

primes = eratosthenes(N).reject{|num| num.to_s[/[024568]/]}

來源

2016-08-31 12:32:10 michau

這似乎給了我兩個不同的答案。如果我運行第一個，我的數組中剩下1111個素數，如果我運行第二個素數，則剩餘3217個素數。 –

啊，對不起，我沒有注意到你的名單中包含5，我以爲它只是偶數。我編輯了我的答案，現在就試試。 – michau

我認爲你正在尋找的東西，如：

primes.reject!{|num| num % 2 == 0}

來源

2016-08-31 12:27:46

任務不是去除偶數（除2之外的素數都不是），而是包含偶數位的所有數字。 – michau

這對我已經形成的素數列表沒有任何影響，因爲沒有素數將被均分2.我想要我的程序要做的是去除素數像23,47,277等，因爲他們有2,4和2在他們分別。 –

搜索特定數字的大數字列表的效率

回答

相關問題