Ciaran S - 3 months ago 12

Ruby Question

I have the following code where

`eratosthenes(N)`

`eratosthenes(N)`

`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

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]/]}
```

Source (Stackoverflow)

Comments