Faster algorithm for primality test

Prime numbers are those positive integers that are divisible only by 1, and itself. For example 2 is a prime number. So are 3, 5, 7, 11, 13, and 17. All of these have exactly two divisors, 1, and the number itself. 1 was considered as a prime for a long time, before it was declared to be not a prime.

How would you implement a function that should return true or false based on whether the number passed as argument is a prime or not?

bool isPrime(long n)

{ … }

A naive algorithm is to divide the number by all integers starting from 2 to n-1, and see if any one of them is a divisor. If yes, “n” is not a prime, otherwise, a prime.

This is fast enough when you have a small number of integers to test for primality. But as the number of test cases grow, this algorithm proves to be very slow.

A way to make it faster is to reduce the number of divisions we have to perform. Instead of testing from 2 to n-1, you could get away by testing with integers only from 2 to sqrt(n). This is because if there are any divisors of “n” other than 1 and n itself, half of them have to be smaller than or equal to sqrt(n). To see why this is true, analyse that for any divisor “x” of “n” greater than sqrt(n), there has to be a corresponding divisor “y”, less than sqrt(n), such that x*y==n, and vice versa. Take the example of n=100. Divisors other than 1 and 100 itself are: 2, 4, 5, 10, 20, 25 and 50. The divisors less than sqrt(100) are 2, 4, and 5. Their corresponding partners from divisors greater than sqrt(n) are 50,  25, and 20. Thus if there is no divisor less than or equal to sqrt(n), there is no divisor greater than it either, and n is prime.

Primality test

We can also ignore dividing by even numbers, since every prime greater than 2 is odd. If an integer is even and greater than 2, it has 2 as its divisor and thus isn’t a prime.

Another fact is that every prime greater than 3 can be written in the form 6k+/-1. To explain why this is true, analyse that all integers greater than 4 can be divided into the following 6 groups:

  1. 6k – 1
  2. 6k
  3. 6k + 1
  4. 6k +2
  5. 6k + 3
  6. 6k + 4

Other values such as 6k + 5/6/7 etc are already covered by previous groups. For example -1 is congruent to 5 modulo 6. So 6k + 5 is actually 6k – 1 for k increased by 1.

Out of the 6 groups, only group 1 and group 3 CAN be primes (but may not be). The others can’t be because they have 6, 2, 3, and 2 as their divisors respectively. This leads to the fact that we can test “n” for primality by dividing with integers 2, 3, and all integers in the form of 6k+/-1 that are greater than 4 and less then sqrt(n), since either “n” is prime, or it most certainly will have one of those integers as its divisor.

Thus keeping these facts in mind, a faster algorithm for primality test is as following (implemented in C++):

Be Sociable, Share!

Leave a Reply