On Fri, Apr 13, 2012 at 8:09 AM, Peter H. <

[email protected]> wrote:

Actually there are better ways to check for prime numbers between a

and b (hint: 2 is the only *even* prime, why are you even looking at

any others?)

In the same way you can rule out all all multiples of 2, you can rule

out

all multiples of 3 and 5 and 7 and so on. This means you only need to

see

if your number is divisible by any primes (if it is divisible by 4 or 6

or

8, then it is also divisible by 2).

So we can write it like this:

def prime(upper_limit)

return [] if upper_limit < 2

(3…upper_limit).each_with_object [2] do |potential_prime, primes|

next if primes.any? { |prime| potential_prime % prime == 0 }

primes << potential_prime

end

end

prime 1 # => []

prime 2 # => [2]

prime 3 # => [2, 3]

prime 4 # => [2, 3]

prime 5 # => [2, 3, 5]

prime 6 # => [2, 3, 5]

prime 7 # => [2, 3, 5, 7]

prime 8 # => [2, 3, 5, 7]

prime 9 # => [2, 3, 5, 7]

prime 10 # => [2, 3, 5, 7]

prime 11 # => [2, 3, 5, 7, 11]

prime 12 # => [2, 3, 5, 7, 11]

prime 13 # => [2, 3, 5, 7, 11, 13]

prime 14 # => [2, 3, 5, 7, 11, 13]

prime 15 # => [2, 3, 5, 7, 11, 13]

prime 16 # => [2, 3, 5, 7, 11, 13]

prime 17 # => [2, 3, 5, 7, 11, 13, 17]

prime 18 # => [2, 3, 5, 7, 11, 13, 17]

prime 19 # => [2, 3, 5, 7, 11, 13, 17, 19]

prime 20 # => [2, 3, 5, 7, 11, 13, 17, 19]

If we wanted to get elaborate, we could introduce a cutoff at the square

root:

def prime(upper_limit)

return [] if upper_limit < 2

(3…upper_limit).each_with_object [2] do |potential_prime, primes|

cutoff = Math.sqrt potential_prime

next if primes.take_while { |prime| prime <= cutoff }.any? { |prime|

potential_prime % prime == 0 }

primes << potential_prime

end

end

If you needed this to be super fast, there would be better ways to write

this (as in faster, but harder to understand and read), but this shows

the

basic idea.