Why does the +6 Iteration Method Work for Testing Prime Numbers?

4 min readApr 12, 2016

This method works by not bothering to check numbers for primality if we can reason in advance that they are not prime. We are going to write a small function that builds a list of prime numbers of length n or greater, to explain this method. In order to isolate the issue, we will not try to increase the efficiency of the function in any additional way, so no memoization etc.

Firstly, we will assume the existence of a function isPrime, that tests a single number for primality.

With our magical isPrime method, we could build a list of prime numbers like this:

 
function makePrimeArray(n) {
    var primes = [];
 
     for (var integer = 0; primes.length < n; integer++) {
     if (isPrime(integer)) primes.push(integer);
     }
 
     return primes;}

But iterating through every single integer is pretty wasteful. As humans, we would probably cut our work in half straight away by not checking even numbers greater than two. After all, an even number is just a number divisible by two, and therefore definitely not a prime.

Lets update the makePrimeArray function to reflect this:

function makePrimeArray(n) {
 
    //include all primes smaller than our for loop will test for
    var primes = [2];
 
    /*
     *iterate through integers in jumps of 2
     *check all the numbers that are not even for primality
     *until we have enough primes
     */
    for (var evenNumber = 2; primes.length < n; evenNumber += 2) {
    if (isPrime(evenNumber + 1)) primes.push(evenNumber + 1);
    }
 
    return primes;
}

Hopefully you can see that by landing on every even number, and testing the number one higher than it, we are testing all odd numbers that are greater than 2.

To phrase this in another way: we know that all multiples of 2 are not prime numbers, so we are decreasing the total number of iterations by only checking numbers that are not multiples of 2.

Put like this, we can see that the choice of 2 is pretty arbitrary. Could we not instead check only numbers that are not multiples of 3?

function makePrimeArray(n) {
 
 //include all primes smaller than our for loop will test for
 var primes = [2, 3];
 
  
 /*
  *iterate through integers at intervals of 3
  *test only the numbers that are not multiples of three for
  *primality
  */
 for (var multipleOf3 = 3; primes.length < n; multipleOf3 += 3) {
   if (isPrime(multipleOf3 + 1)) primes.push(multipleOf3 + 1);
   if (isPrime(multipleOf3 + 2)) primes.push(multipleOf3 + 2);
 }
 
 return primes;
}

When multipleOf3 is 3, we test 4 and 5 for primality
When multipleOf3 is 6, we test 7 and 8 for primality
When multipleOf3 is 9, we test 10 and 11 for primality

In this way, we skip multiples of three, but test all other numbers.

Lets write it one more time, testing only numbers that are not a multiple of 6:

function makePrimeArray(n) {
 
 //include all primes smaller than our for loop will test for
 var primes = [2, 3, 5];
 
 for(var multipleOf6 = 6; primes.length < n; multipleOf6 += 6) {
  if (isPrime(multipleOf6 + 1)) primes.push(multipleOf6 + 1);
  if (isPrime(multipleOf6 + 2)) primes.push(multipleOf6 + 2);
  if (isPrime(multipleOf6 + 3)) primes.push(multipleOf6 + 3);
  if (isPrime(multipleOf6 + 4)) primes.push(multipleOf6 + 4);
  if (isPrime(multipleOf6 + 5)) primes.push(multipleOf6 + 5);
 }
 
 return primes;}

When multipleOf6 is 6, we test 7, 8, 9, 10, 11 for primality etc…

But wait, we say. This is starting to look very inefficient again. When we were iterating through multiples of two, we only test 1/2 of all integers (all the odd numbers). Now we are testing 5 out of every 6! What more improvements can we make?

Well 6 has a special property that makes it a good interval for this iteration:

6 = 2 x 3

Two and three are both factors of 6.

This means that every multiple of 6 is also a multiple of two, and is also a multiple of 3. A few examples:

12 = 6 x 2 = 2 x 6 = 3 x 4
18 = 6 x 3 = 2 x 9 = 3 x 6
24 = 6 x 4 = 2 x 12 = 3 x 8

Follow the 6 times-table up if you want to convince yourself further.

How does this help? Well, we know from our previous reasoning that if a number is divisible by two, then that number + 2 is also divisible by 2. Or to put another way, if we know that one number is even, we know that if we add two to it, we will get another even number.

As we are iterating through multiples of 6, we know that every number that we land on as multipleOf6 will be an even number (is a multiple of 2). Therefore, the number that is 2 higher than it (multipleOf6 + 2) and two higher again than that (multipleOf6 + 4) will also be even. So we don’t have to check those numbers for primality — we already know that even numbers are not prime. We can remove the tests for this set of numbers entirely.

Our updated function:

function makePrimeArray(n) {
 var primes = [2, 3, 5]
 
 for(var multipleOf6 = 6; primes.length < n; multipleOf6 += 6){
 if (isPrime(multipleOf6 + 1)) primes.push(multipleOf6 + 1);
 if (isPrime(multipleOf6 + 3)) primes.push(multipleOf6 + 3);
 if (isPrime(multipleOf6 + 5)) primes.push(multipleOf6 + 5);
 }
 
 return primes;
}

You can probably guess the final improvement yourself now. As we know that every number that we land upon as multipleOf6 is also a multiple of 3, the number 3 higher than multipleOf6 will also be a multiple of 3, and therefore not prime. We can skip the test for (mutlipleOf6 + 3).

Our final function:

function makePrimeArray(n) {
 var primes = [2, 3, 5];
 
 for (var multipleOf6 = 6; primes.length < n; multipleOf6 += 6) {
 if (isPrime(multipleOf6 + 1)) primes.push(multipleOf6 + 1);
 if (isPrime(multipleOf6 + 5)) primes.push(multipleOf6 + 5);
 }
 
 return primes;
}

Great! Now we are testing only 1/3 of integers to see if they are prime, instead of every single one. To improve our function further, we could memoize the results or make sure it only returns as many primes as it is asked for.

Written by Laura Thornhill