A Ruby example of using the Sieve of Eratosthenes to determine whether or not a number is prime

Sieve of Eratosthenes.md

Using the Sieve of Eratosthenes to Find Prime Numbers in Ruby

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:

1. Create an array from 0..max
2. Starting at 2, delete every multiple of 2 from the array.
3. Then, go back to the beginning, and delete every multiple of 3.
4. Repeat this starting from the next available number at the beginning of the array.
5. Do this until the square of number you are checking is greater than your max number.
6. 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)

Hello. Firstly, I would like to say thank you for posting this gist. It is both well-thought-out and well-detailed!

I have a good grasp of what is going on and I have stepped through the function with a debugger/byebug in order to wrestle with a deeper understanding of things, but I was wondering if you could clarify something for me.

Within the each loop, on the line where we invoke the step function (reference is below), what is the rationale for the p*p as the numeric starting point? I attempted altering this part to be either p*2 or just simply p. It did not work out well for me. In other words, I am wondering what the reason is behind starting at the exponent of the current number?

(p*p).step(max,p) { |m| primes[m] = nil }

Thank you in advance!

Not the poster, but I can answer this.

Within the each loop, on the line where we invoke the step function (reference is below), what is the rationale for the p*p as the numeric starting point?

This is a clever optimization. Given a number p, it'd be skipped if an earlier entry in the list was a divisor, so p 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 that 2 * p, 3 * p, etc have already been marked nil. What, then, is the first instance of a multiple of p that needs to be marked nil? p * p.

Hope that helps.