Wednesday, 28 December 2016

Checking whether a number is prime or not...


First of all, this must be clear that 1 is neither prime nor composite. To answer why, I found this great answer on Quora which you must read : This answer.

Let n be a number which we want to find whether it is prime or not. Then we do not need to check if it divides any of the number between 2 and ( n - 1). We also do not need to check if it divides any of the number between 2 and n / 2. We only need to check if divides any of the number between 2 and square root of n.


As we can see in the below given graph that sqrt(x) is much less then x / 2. The meeting point of these graph is x = 4 which is very small number and we do not need to be concerned about it.


Plot of the graphs of sqrt(x) and x/2

But the problem is that, as we can see in the below mentioned function IsPrime loop runs sqrt(n) times and we try to conclude that time complexity of the program is O(sqrt(n)) which is not true. The time complexity to check whether a number is prime or not is actually exponential. This is called pseudo-polynomial time. In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric value of the input, but is exponential in the length of the input – the number of bits required to represent it.

These kind of algorithm are called weakly NP - Complete. When the algorithm takes exponential time but a pseudo-polynomial time algorithm exists then it called weakly NP - Complete.

/*See this C code before further reading*/
int IsPrime(int n) {
int i, number = (int)sqrt(n);
for (i = 2; i <= number; i++)
if (n % i == 0)
return 0;
return 1;
}
If you go on Stack Overflow to find the fastest way to check whether a number is prime or not then we will find many answers which claims that they are pretty fast or one-liners but the problem is that many of them are not even giving correct answers. Also some programs are not as fast as they claim it to be. For many general purpose use, my function above gives correct and fast answers.


Also, there is Sieve of Atkin which gives all the primes below a certain number. The pseudo code, explanation and code to Sieve of Atkin can be easily found on the internet. For reference, read Wikipedia and Stack Overflow.

No comments:

Post a Comment