Just realized this fact, but need confirmation if I'm not missing anything (Although it got AC on a problem :P) because it looks simple AF!!
Every integer can be represented as one of the following-> 6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5.
6k -> divisible by 6 (Hence not prime)
6k+1 -> Prime
6k+2 -> Or 2*(3k+1); Hence divisible by 2 (Not prime)
6k+3 -> Divisible by 3 (Not prime)
6k+4 -> Divisible by 2 (Not prime)
6k+5 -> Prime
Therefore, each prime number (>3) can be represented in either 6k+1 form or 6k+5 form.
bool isPrime(int x) {
if (x==1) return false;
if (x==2 || x==3) return true;
//If (x == 6k+1)
int k = (x-1)/6;
if (x == (6*k+1)) return true;
//If (x == 6k+5)
k = (x-5)/6;
return (x == (6*k+5));
}
I dont think this works, for x=35, it is of the form 6k+5 where k=5 but it is not a prime.
25 is 6 * 4 + 1, but not prime.
Primality testing is a complicated problem and unfortunately there isn't such a simple solution.
Your claim ' Each prime number (>3) can be represented in either 6k+1 form or 6k+5 form ' is correct.
Your function, on the other hand, makes the claim:
' Every number of the form 6k+1 or 6k+5 is prime '
which is false.
For example:
25 = 6*4 + 1
35 = 6*5 + 5
49 = 6*8 + 1
and many more
Your assumptions about 6k+1 and 6k+5 cases is wrong.
Counterexample for 6k+1: 25=6*4+1 (k=4)
Counterexample for 6k+5: 35=6*5+5 (k=5)
Thanks guys, That's why I was asking for confirmation, even I felt it should not be that simple.. I guess I should change the title of the post.
P.S. look that the solution link This got an AC. Maybe the testcases were weak.