Constant Time O(1) way to check if number is prime !

Revision en2, by arjitkansal, 2019-10-31 15:47:25

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));
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English arjitkansal 2019-10-31 16:11:27 70
en2 English arjitkansal 2019-10-31 15:47:25 28
en1 English arjitkansal 2019-10-31 15:45:59 832 Initial revision (published)