CODEWITHSUNDEEP
javatime-complexityprimes
Anakar
Anakar

Reputation: 112

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.

Upvotes: 2

Views: 211

Answers (1)

Jason
Jason

Reputation: 11822

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).

Upvotes: 8

Related Questions