Finding Primes with Ruby

A prime number is a number other than 1 that is only divisible by itself and 1. For example, the prime numbers between 1 and 10 are 2, 3, 5, and 7. So just knowing the definition of a prime number gives a huge hint on how to build an algorithm to find all of the prime numbers between 0 and n.

The easiest way to solve this problem is to use trial division. Go through each number n, and check the remainder of dividing n by every number before it besides 1. If you find a number that has a remainder of 0, you know n is not prime. So if n = 9, you say 9 % 2 == 0 #=> false, then 9 % 3 == 0 #=> true. Since you found a true outcome, you know 9 is not prime. Here is an example in code that prints out all prime numbers from 0-n:

This will give the right answers for any input, but you can see it will get exponentially slower as n gets larger. How can we make this better?

Let’s think of some general rules we know about prime numbers that we can apply to the code. What do we know about all numbers? Well, numbers are either even or odd, so we can generally separate numbers into 2 groups. What do we know about even numbers? They are divisible by 2. Therefore, by definition, the only even prime number is 2. Right there we have just reduced the amount of work we have to do by half. So lets add a simple if statement to implement that rule:

Now that we have an idea on how we can make this better, we can expand it to further reduce the numbers we need to check. The logical next step here is to add a rule, for each prime number we find, if the next number to check is divisible by any prior prime number, we can skip it. So we’ll make an array of prime numbers we have already found, then check the next numbers against each prime we have already found. Here is the code:

Let’s verify this actually works with some benchmarking. We’ll use n = 20,000 to demonstrate the time difference. Here is the code:

Here are the results:

Now we have seen a few different ways to find prime numbers, and explored how to make it faster. For further reading on this, check out the Sieve of Eratosthenes.