The Sieve of Eratosthenes is a super efficient way to determine whether or not numbers are prime. Essentially, it takes a max number, and via the process of elimination, gives you an array that contains every prime number up to that max number.
The very short explanation is this:
- Create an array from 0..max
- Starting at 2, delete every multiple of 2 from the array.
- Then, go back to the beginning, and delete every multiple of 3.
- Repeat this starting from the next available number at the beginning of the array.
- Do this until the square of number you are checking is greater than your max number.
- Finally, compact the original array.
This array will then contain only the prime numbers up to your max number. You'll find that it's really, really efficient. So efficient that you can use it as a helper method to determine whether or not a number is prime. Want to know if the number 105557 is prime? Only takes 66 steps.
Here's Ruby code, with comments. (The counter
variable is totally unnecessary and is just used for benchmarking):
def sieve(max)
# Set up an array with all the numbers from 0 to the max
primes = (0..max).to_a
# Set both the first and second positions (i.e., 0 and 1) to nil, as they
# aren't prime.
primes[0] = primes[1] = nil
# Iterate through primes array
counter = 0
primes.each do |p|
# Skip if nil
next unless p
# Break if we are past the square root of the max value
break if p*p > max
counter += 1
# Start at the square of the current number, and step through.
# Go up to the max value, by multiples of the current number, and replace
# that value with nil in the primes array
(p*p).step(max,p) { |m| primes[m] = nil }
end
# Finally, return the compacted array.
puts "Solved for #{max} in #{counter} steps."
primes.compact
end
def prime?(num)
sieve(num).include?(num)
end
puts prime?(105557)
Ruby happens to have this built in, actually. You can use the Prime
module and an object called EratosthenesGenerator
to do the same thing. In code, if you wanted to see if the number 105557
is prime, you'd do the following:
require 'prime'
num = 105557
primes = Prime::EratosthenesGenerator.new.take_while {|i| i <= num}
primes.include?(num)
Not the poster, but I can answer this.
This is a clever optimization. Given a number
p
, it'd be skipped if an earlier entry in the list was a divisor, sop
is prime and needs to stay in the list. Since all the earlier primes in the list have had their multiples marked nil, you know that2 * p
,3 * p
, etc have already been marked nil. What, then, is the first instance of a multiple ofp
that needs to be marked nil?p * p
.Hope that helps.