Understanding Prime Numbers Better And Code A Decent Primality Test

 This tutorial aims to help you understand prime numbers in a whole new level, although you won't be an expert on the topic, you'll understand so much better how they work and how to code a pretty decent, good looking primality test (which could be a job interview exercise) and impress a few.

First let's give a look to the definition of prime number:
"An integer greater than one is called a prime number if its only positive divisors (factors) are one and itself."[1]

Here's the answer to a common question about prime numbers: Why is 1 (one) not a prime? Answer: 1 (one) is not a prime by definition, because the definition of a prime number says that "An integer greater than one is called a prime number..." [2]

Level 1

Now let's think of the simplest (slowest) way of testing whether a number is prime (primality test): We divide n (the number we are testing) by all the numbers greater than 2 and lower than n/2. This is because 2 is the lowest integer that could be factor of n so n/2 would be the greatest integer that could be factor of n. Example: for n = 100, we'd test from 2 to 49, since testing factor 2, we've already tested factor 50, 50*2=100.

Using this method to test n = 997 (which is prime) we'd have to go through the range: 2,3,4...497. Bellow you'll find the code snippet for this level:

01	int isPrime( unsigned long n)

02

{

03	if( n < 2)

04

return 0;

05

06	unsigned long test = 2;

07

08	while( test < n/2 )

09

{

10	if( n%test == 0 )

11	return 0; // test is a factor of n thus n is NOT prime

12

test++;

13

}

14

15	// we've tested all numbers lower than greatest POTENTIAL factor of n, we can say n is prime

16

return 1;

17

}

Level 2

For this level we need to understand two more things about divisibility/factors:

• Divisibility by the first three primes: if we know that a number is greater than 2 AND is divisable by 2, we know for a fact it's not a prime, same thing applies for 3 and 5. Example: 18 = 9*2, 9 = 3*3, 15 = 3*5.
  
  
• Greatest factors of an integer: let's recall the definition of prime and stop for a second to think, we're are not looking for a lot of numbers/factors, it only takes one extra factor aside 1 and n (itself) for n not to be prime. So we're only testing whether the number in question fits an equation of the form: n = x*x, in other words, if we multiply TWO numbers and we have as a result n, then n is NOT prime.

Let's review a quick example with the number 17:

2*2 = 4, 2*3 = 6, 2*4 = 8, 2*5 = 10, 2*6 = 12, 2*7 = 14, 2*8 = 16, 2*9 = 18
3*3 = 9, 3*4 = 12, 3*5 = 15, 3*6 = 18
4*4 = 16, 4*5 = 20
5*5 = 25

If you pay attention to the example, the greatest possible factors lower than 17 are 4*4. This means that, in order to test the most possible amount of factors (x*y) without going further than n, we need to test all the numbers lower greater than 2 and lower than √n. You can always represent this as: x*y < n.

This way, we're only testing all numbers from 5 to square root of n, removing from the beginning any number divisible by 2 or 3. This is a lot faster than level 1 but we can still reach one more level.

Using this method to test n = 1009 (which is prime) we'd have to go through the range: 5...31 (since 32*32 = 1024). Bellow a code snippet for this level:

01	int isPrime( unsigned long n)

02

{

03	if( n < 2 ) // 1 is not prime

04

return 0;

05	if( n <= 3 ) // 2 and 3 are primes

06

return 1;

07	if( n%2 == 0 || n%3 == 0)// n is not prime if can be divided by 2 or 3

08

return 0;

09

10	unsigned long test = 5; // at this point we've tested 1,2,3 and 4 and all the numbers divisable by them

11

12	while(test*test < n)

13

{

14	if( n%test == 0 )

15	return 0; // test is a factor of n thus n is NOT prime

16	test++;// we're still adding one per iteration

17

}

18

19	// we've tested all numbers lower than greatest POTENTIAL factor of n, we can say n is prime

20

return 1;

21

}

Level 3

This is the last level on this tutorial. We're going to review a Wikipedia article to explain this: "We can improve this method further. Observe that all primes greater than 3 are of the form 6k ± 1, where k is any integer greater than 0. This is because all integers can be expressed as (6k + i), where i = −1, 0, 1, 2, 3, or 4."

Let's see a few example of this form:
17 = 6(3) + (-1), k=3, i=-1
24 = 6(4) + (0), k=4, i=0
391 = 6(65) + (1), k=65, i=1
22 = 6(3) + (4), k=3, i=4

"Note that 2 divides (6k + 0), (6k + 2), and (6k + 4) and 3 divides (6k + 3). So, a more efficient method is to test whether n is divisible by 2 or 3, then to check through all numbers of the form 6k ± 1 < √n. This is 3 times faster than testing all numbers up to √n." [3]

01	int isPrime( unsigned long n)

02

{

03	if( n < 2 ) // 1 is not prime

04

return 0;

05	if( n <= 3 ) // 2 and 3 are primes

06

return 1;

07	if( n%2 == 0 || n%3 == 0)// n is not prime if can be divided by 2 or 3

08

return 0;

09

10	unsigned long test = 5; // at this point we've tested 1,2,3 and 4 and all the numbers divisable by them

11

12	while(test*test < n)

13

{

14	if( n%test == 0 || n%(test+2) == 0 ) // Remember k should be greater than one, so we test like: (6k-1 || 6k+1)

15

return 0;

16	test+=6;// Now we are adding 6 per iteration because we are following the form 6k ± 1

17

}

18

19	// We can say n is prime

20

return 1;

21

}

Here there's one more important thing to see: We have 1, 2, 3, 4, 5, 6, 7, 8 and 9 as the base of all the rest of the integers but as we already tested for 2 and 3, then we've already tested for 4, 6 and 9 too since 2 and 3 are factors of them. Furthermore, we're testing by the form 6k ± 1 which eliminates all integers of the form (6k + 0), (6k + 2), (6k + 4) and (6k + 3).

That leave us with 5 and 7 and all the numbers that can be divided by them but also with 11, 13, 17, 19, 23..., and all the numbers that can be divided by them.

In conclusion, this "Level 3" primality test leave us with only the prime numbers and the numbers that could be divided by them, for example: 39 which is 13*3 or 119 = 17*7.

This is, in my opinion, the best way to write a primality test in terms of a good balance of effort, complexity of the algorithm and speed although we can review more complex methods on a new tutorial.

If you enjoyed this tutorial, please do not forget to click on the green (+) button. />