0

I was reading about primality test and at the wikipedia page it said that we just have to test the divisors of n from 2 to √n

This part about √n is fine But the next part is hard to understand quote :

"The algorithm can be improved further by observing that all primes are of the form 6k ± 1, with the exception of 2 and 3. This is because all integers can be expressed as (6k + i) for some integer k and for i = −1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3). So, a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form
6 K ±1≤ √n "

What does it mean by saying :to check through all the numbers of form 6K ±1≤ √n ?

Can someone explain it ?

xuoimai
  • 89
  • 1
    That you do not try to divide $n$ with every number lower than $\sqrt n$, but only with those of the form $6k+1$ or $6k-1$. So, you test only these numbers: 5,7,11,13,17,19,23,25,29,31,35,37... etc. because trying to divide it with others has no point, since they are all divisible by $2$ or $3$, so you'd be doing a redundant work, because you already know $n$ is not divisible by those two. – TStancek Sep 21 '17 at 09:35
  • Got it thank you.I forgot the part check n is divisible by 2 or 3 first – xuoimai Sep 21 '17 at 11:29

1 Answers1

0

This is because you might not have a list of the primes. Suppose you want to check if $10^{50}+1$ is prime. You might not have a list of all the primes, and it is tedious to look for them.

Knowing that every prime is of the form $6k\pm 1$, you divide $n$ by every number less than $\sqrt{n}$ that is of the form $6k \pm 1$. If none of them divide $n$ it must be prime.

Computationally, this is more efficient than having to look for the primes less than $n$ before checking if they divide $n$.

Sofía Marlasca Aparicio
  • 3,238