Prime Numbers and Basic Primality Tests - SPOJ - Prime1

Prime numbers are the numbers which get divided properly (leaving remainder as 0) only by 1 and the same number.

The same way, numbers which get divided by 1, the same number and other numbers are called composite numbers.

Current state of the art security infrastructures rely on security schemes such as RSA and DSA. They both, in turn, rely heavily on Prime numbers. So prime numbers are so important in the digital world's security. Lets see few of the algorithms to determine whether the given number is a Prime number or not.

Basic Tests for Primality

Lets say, we want to find whether the numbers 101 and 100 are prime numbers are not.

Approach 1

This is the very basic approach and very easy to implement.

• Read the number n
• Loop with i from 2 till n/2 (if it doesn't divide properly, round off is needed)
• if i divides n with out leaving any remainder (remainder is 0) then return false
• End Loop
• return true

The idea here is to check whether each and every number from 2 till half of that number [2, n/2] divides the number or not. If any of them divides the number without leaving any remainder, we can declare that the number is NOT a prime number. If no number in that range divides properly, the number is called a Prime number. We check only till n/2, because 2 * n/2 would be n, there would be no number greater than n/2 would divide n properly. In the worst case, It needs n/2 iterations to confirm whether the number is prime or not. In our case, for 101, it is 50.

Approach 2

The simplicity of this algorithm would tempt us to use this always. Lets see, if we can improve this. If we observe closely, if the number n is odd, we don't even have to try any of the even numbers. This would reduce the number of iterations needed by half.

• Read the number n
• if n is even return false
• Loop with i from 3 till n/2, increment i by 2
• if i divides n with out leaving any remainder (remainder is 0) then return false
• End Loop
• return true

As we can clearly see, if n is even it can not be a prime number, since if a number is even it is divisible by 2. So we check only the odd numbers starting from 3 till n/2 and we are skipping all the even number  by incrementing the loop's index variable by 2 every time. So the loop would be run for the values 3,5,7,9, 11... Now if we look at the performance of this approach, we just need n/4 iterations to find whether the number is a prime number or not. In our case, for 101, it is 25.

Approach 3

Lets see, if we can reduce it further from n/4. Lets write down the combinations which would yield 100. {2, 50}, {4, 25}, {5, 20} and {10, 10}. Lets try 256. {2, 128}, {4, 64}, {8, 32}, {16, 16}. In both the cases, atleast one of the numbers is always lesser than equal to the square root of the actual number. (I, honestly, don't know how to prove this, but this observation works always). So, instead of looping till n/2 we are going to limit the loop at square root of the number. Combining the observation we made in approach 2, presenting approach 3.

• Read the number n
• if n is even return false
• Loop with i from 3 till sqrt (n), increment i by 2
• if i divides n with out leaving any remainder (remainder is 0) then return false
• End Loop
• return true

In our case, we see a tremendous hike in performance, for the value 101, in the worst case we might have to do only 4 checks.

Approach 4

We have already had good performance with approach 3. Lets see if we still can improve it. Lets list the four values with which we may need to divide 101 to determine whether it is prime or not. The values are {2, 3, 5, 7, 9}. We have 2 as well here, since we check whether the input is even or not and 11 is not included because sqrt (101) would be rounded off to 10. The odd item in the list is 9, since we are checking against all the odd number between 2 and sqrt(n). We all know that, any given composite (non-prime) number can be expressed in terms of its prime factors. So we can try and divide the number only with the prime numbers within the range [2, sqrt(n)]. Note: This approach works only when we have a predetermined list of prime numbers. If we don't have that its better to stick to approach 3 or have a look at approach 5 below.

Approach 5

Lets observe the list the prime numbers a bit.

{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101...}

Lets rewrite them like this

{2, 3, 6*1-1, 6*1+1, 6*2-1  6*2+1  6*3-1  6*3+1  6*4-1  6*5-1  6*5+1  6*6+1  6*7-1  6*7+1,  6*8-1  6*9-1, 6*10-1, 6*10+1, 6*11+1, 6*12-1, 6*12+1, 6*13-1, 6*14-1, 6*15-1, 6*16+1, 6*17-1...}

Basically, the prime numbers are of the form (6*x)±1 (though few of them may not be prime numbers). This reduces the possible values to be looked at, to a greater extent. 

• Read the number n
• if n is even return false
• if 3 divides n properly return false
• Loop with i from 1 till (6 * i) -1 > sqrt (n), increment i by 1 every time
• if (6 * i) -1 or (6 * i) + 1 divides n with out leaving any remainder (remainder is 0) then return false
• End Loop
• return true

This method would be the fastest of all the methods discussed, I believe.

Based on the ideas discussed above, I managed to solved the SPOJ's PRIME1 problem. The problem description can be found here http://www.spoj.pl/problems/PRIME1/

Spoiler alert: This http://ideone.com/4n9kB has my solution to the above mentioned PRIME1 problem.