Sieve of Eratosthenes
In working on Project Euler's 'Largest prime factor' problem I wanted a better way to find primes in a range than brute force testing each number. After a little research I found the "Sieve of Eratosthenes". (What a great name.)
The idea is, instead of iterating through each number in a range and testing if it's prime; when you find a prime, remove all of it's multiples from the range, then continue iterating. So in the 1-100 example, finding 2 lets you get rid of 49 possibilities (all the evens except for 2) and finding 3 lets you eliminate 32 more. So almost right away you've gone from iterating through 100 possibilities to 19.
It's one of the most efficient ways to find prime numbers up to about 10,000,000 according to Wikipedia and a couple other sources I found.
Ruby's Prime
class has an Eratosthenes Generator which you can use to, well, generate prime numbers of course.
irb > require 'Prime'
irb > prime_generator = Prime::EratosthenesGenerator.new
=> #<Prime::EratosthenesGenerator:0x000001011aaa20 @last_prime_index=-1, @ubound=nil>
irb > primes = []
irb > 10.times do
irb > primes << prime_generator.next
irb > end
=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Because I want to better understand ol' Eratosthenes and I need a range of primes between x and y, I wrote my own method.
require 'prime'
def eratosthenes_sieve(num)
raise "#{num} is too big a number for eratosthenes_sieve. Please enter a number under 10000000." if num > 9999999
raise "2 is the first prime number. Please enter a number of 2 or greater." if num < 2
range = (2..num).to_a
range.each do |number|
if number.prime?
# puts "#{number} is prime"
range.each_with_index do |p, i|
if p % number == 0 && p > number
range.delete_at(i)
# puts "Deleting #{p}"
end
end
end
end
range
end
A couple notes:
- This includes a
raise
in case someone tries to use it with too big a number. Above that number the sieve isn't as efficient and the process would run for a long time taking up a lot of memory. - With a large number it can take a while so there are 2
puts
statements that can be commented out to watch it work.
I think it could be more efficient so I'm going to work on improving it in the next couple weeks. Having a prime generator seems pretty handy!