Anakar Parida 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.

Answer Source

It is correct to say that every prime (except for 2 and 3) has a remainder of 1 or 5 when divided by 6 (see this page for a deeper explanation). However, the opposite is not true. Not every number that has a remainder of 1 or 5 when divided by 6 is a prime.

Take 35 for example. It has a remainder of 5 when divided by 6, however it is not a prime (35 = 5 x 7).

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download