Explanation
The algorithm completely ignores any numbers divisible by two, three, or five. All numbers with an even modulo-sixty remainder are divisible by two and not prime. All numbers with modulo-sixty remainder divisible by three are also divisible by three and not prime. All numbers with modulo-sixty remainder divisible by five are divisible by five and not prime. All these remainders are ignored.
All numbers with modulo-sixty remainder 1, 13, 17, 29, 37, 41, 49, or 53 have a modulo-four remainder of 1. These numbers are prime if and only if the number of solutions to 4x2 + y2 = n is odd and the number is squarefree (proven as theorem 6.1 of).
All numbers with modulo-sixty remainder 7, 19, 31, or 43 have a modulo-six remainder of 1. These numbers are prime if and only if the number of solutions to 3x2 + y2 = n is odd and the number is squarefree (proven as theorem 6.2 of).
All numbers with modulo-sixty remainder 11, 23, 47, or 59 have a modulo-twelve remainder of 11. These numbers are prime if and only if the number of solutions to 3x2 − y2 = n is odd and the number is squarefree (proven as theorem 6.3 of).
None of the potential primes are divisible by 2, 3, or 5, so they can't be divisible by their squares. This is why squarefree checks don't include 22, 32, and 52.
Read more about this topic: Sieve Of Atkin
Famous quotes containing the word explanation:
“Are cans constitutionally iffy? Whenever, that is, we say that we can do something, or could do something, or could have done something, is there an if in the offing—suppressed, it may be, but due nevertheless to appear when we set out our sentence in full or when we give an explanation of its meaning?”
—J.L. (John Langshaw)
“There is no explanation for evil. It must be looked upon as a necessary part of the order of the universe. To ignore it is childish, to bewail it senseless.”
—W. Somerset Maugham (1874–1965)
“Natural selection, the blind, unconscious, automatic process which Darwin discovered, and which we now know is the explanation for the existence and apparently purposeful form of all life, has no purpose in mind. It has no mind and no mind’s eye. It does not plan for the future. It has no vision, no foresight, no sight at all. If it can be said to play the role of the watchmaker in nature, it is the blind watchmaker.”
—Richard Dawkins (b. 1941)