Ciaran S - 1 year ago 78
Ruby Question

# Efficiency of searching a large list of numbers for certain digits

I have the following code where

`eratosthenes(N)`
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 (
`eratosthenes(N)`
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) }
primes.delete(num)
end
end
``````

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]/]}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download