Anakar Parida - 4 years ago 66

Java Question

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.

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

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