Ciaran S Ciaran S - 1 year ago 49
Ruby Question

Efficiency of searching a large list of numbers for certain digits

I have the following code where

returns an array of primes from 1 to N. What I want to do is remove any numbers from this list that contain the digits 0, 2, 4, 5, 6, 8. My code seems quite inefficient and wrong as it takes about 20 seconds (
is instantaneous) to get to just 100,000 and doesn't remove all the numbers I want it to. Is there a better, scalable solution to this problem?

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) }

Answer Source

The problem with your approach is that each delete rewrites the array, and it's called for every deleted item, so the complexity of the algorithm is O(n^2) instead of O(n).

You should do something like this:

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

Or simply:

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

It's just a matter of style, but I'd put everything together in one line (note the lack of ! in reject here):

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