Efficacité de la recherche d'une grande liste de nombres pour certains chiffres

Question

J'ai le code suivant où eratosthenes(N) retourne un tableau de nombres premiers de 1 à N. Ce que je veux faire est de supprimer les nombres de cette liste qui contiennent les chiffres 0, 2 , 4, 5, 6, 8. Mon code semble assez inefficace et mauvais car il faut environ 20 secondes (eratosthenes(N) est instantané) pour arriver à seulement 100 000 et ne supprime pas tous les numéros que je le veux. Existe-t-il une meilleure solution évolutive à ce problème?

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 

Answer 1

Le problème avec votre approche est que chaque delete réécrit le tableau, et il est appelé à tous les éléments supprimés, de sorte que la complexité de l'algorithme est O (n^2) au lieu de O (n).

Vous devriez faire quelque chose comme ceci:

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

Ou simplement:

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

Il est juste une question de style, mais je mettrais tout ensemble dans une ligne (notez l'absence de ! en reject ici):

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

Answer 2

Je pense que vous cherchez quelque chose comme:

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