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

Правка en1, от arjitkansal, 2019-10-31 15:45:59

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

}

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский arjitkansal 2019-10-31 16:11:27 70
en2 Английский arjitkansal 2019-10-31 15:47:25 28
en1 Английский arjitkansal 2019-10-31 15:45:59 832 Initial revision (published)