Anakar Parida - 4 years ago 66
Java Question

# Primality Check

Every prime number is in the form of 6k+1 or 6k-1. In order to check if a number is prime or not we can use the below algorithm. I have seen programs that are written based on these algorithms.

``````public boolean isPrime(int n)
{

if (n <= 1)  return false;
if (n <= 3)  return true;

if (n%2 == 0 || n%3 == 0) return false;

for (int i=5; i*i<=n; i=i+6)
if (n%i == 0 || n%(i+2) == 0)
return false;

return true;
}
``````

But I don't understand what would have been the problem if we had written code in the following manner:

``````public boolean isPrime(int number){
boolean primeFlag = false;
if(number == 0 || number ==1){
return primeFlag;
}
if(number == 2 || number == 3){
primeFlag = true;
}
if((number+1)%6 == 0){
primeFlag = true;
}
if((number-1)%6 == 0){
primeFlag = true;
}
return primeFlag;
}
``````

By this we can reduce the time complexity to O(1) compared to O(root(n)). Please let me know if am heading towards wrong direction.