0

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
3
  • "that contain the digits 0, 2, 4, 5, 6, 8" - I'm pretty sure that's a wrong approach for efficient Eratosthenes' sieve. You want to skip the numbers where its last digit is one of those, don't you? Aug 31, 2016 at 12:20
  • Also, don't mutate the array you're currently iterating. This should explain the "doesn't remove all the numbers I want it to" Aug 31, 2016 at 12:21
  • My reasons for removing 0, 2, 4, 5, 6, 8 are separate to my initial search for primes. I already have my primes array and I want to cull that further. Second point is duly noted.
    – Ciaran
    Aug 31, 2016 at 12:33

2 Answers 2

1

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]/]}
2
  • This seems to give me two different answers. If I run the first one I get 1111 primes left in my array and if I run the second I have 3217 primes remaining.
    – Ciaran
    Aug 31, 2016 at 12:44
  • Ah, sorry, I didn't notice your list includes 5, I thought it was only even numbers. I've edited my answer, try it now.
    – kxmh42
    Aug 31, 2016 at 12:46
0

I should think that you're looking for something like:

primes.reject!{|num| num % 2 == 0}
2
  • The task is not to remove even numbers (primes other than 2 aren't even anyway), but all numbers that contain even digits.
    – kxmh42
    Aug 31, 2016 at 12:35
  • This does nothing for my already formed list of primes seen as none will be evenly divided by 2. What I'm looking for my program to do is remove primes like 23, 47, 277 etc. because they have 2, 4 and 2 in them respectively.
    – Ciaran
    Aug 31, 2016 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.