Title: Primality Check
Tags: java;time-complexity;primes
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.

Comment: No.  2 and 3 are exceptions to your stated rule; neither are of the stated form..  In effect you are looking at a 2,3 wheel factorisation.  Some internet research will help.

Here is the accepted answer: 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).

Comment for this answer: Thanks a lot. That explains everything.


{'source': 'StackExchangeDataset', 'subset': 'stackoverflow.com', 'metadata': {'AnswerCount': 1, 'CommentCount': 1, 'ContentLicense': 'CC BY-SA 3.0', 'CreationDate': '2016:00:07/08/16', 'FavoriteCount': None, 'PostTypeId': 1, 'Tags': '<java><time-complexity><primes>', 'Title': 'Primality Check', 'ViewCount': 170, 'id': 38258627, 'user_AboutMe': '', 'user_AccountId': 5256746.0, 'user_DisplayName': 'Anakar', 'user_Reputation': 102.0, 'user_Views': 20.0, 'user_id': 4199424.0}}