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; | |

} |

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