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:
“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)
“Young children constantly invent new explanations to account for complex processes. And since their inventions change from week to week, furnishing the “correct” explanation is not quite so important as conveying a willingness to discuss the subject. Become an “askable parent.””
—Ruth Formanek (20th century)
“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)