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:
“Auden, MacNeice, Day Lewis, I have read them all,
Hoping against hope to hear the authentic call . . .
And know the explanation I must pass is this
MYou cannot light a match on a crumbling wall.”
—Hugh MacDiarmid (1892–1978)
“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)
“My companion assumes to know my mood and habit of thought, and we go on from explanation to explanation, until all is said that words can, and we leave matters just as they were at first, because of that vicious assumption.”
—Ralph Waldo Emerson (1803–1882)