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.