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 ?
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$.