arjitkansal's blog

Seemed to be a Constant Time O(1) way to check if number is prime (confirmation required but now proved to be incorrect!!)
By arjitkansal, history, 5 years ago, In English

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));
}
  • Vote: I like it
  • -62
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I dont think this works, for x=35, it is of the form 6k+5 where k=5 but it is not a prime.

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

25 is 6 * 4 + 1, but not prime.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply