Analysis and Computer Implementation
Given a number k > n, we know that it is not prime if k mod n and n are not relatively prime. The fraction of numbers that the wheel sieve eliminates is 1 - phi (n) / n, which is also the efficiency of the sieve. From the properties of phi, it can easily be seen that the most efficient sieve smaller than x is the one where and . It can also be demonstrated that this efficiency rises very slowly for large n.
To be of maximum use on a computer, we want the numbers that are smaller than n and relatively prime to it as a set. Using a few observations, the set can easily be generated :
- Start with, which is the set for .
- Let be the set where k has been added to each element of .
- Then where represents the operation of removing all multiples of x.
- 1 and will be the two smallest of when removing the need to compute prime numbers separately
- The set is symmetrical around, reducing storage requirements.
Read more about this topic: Wheel Factorization
Famous quotes containing the words analysis and/or computer:
“... the big courageous acts of life are those one never hears of and only suspects from having been through like experience. It takes real courage to do battle in the unspectacular task. We always listen for the applause of our co-workers. He is courageous who plods on, unlettered and unknown.... In the last analysis it is this courage, developing between man and his limitations, that brings success.”
—Alice Foote MacDougall (1867–1945)
“The computer takes up where psychoanalysis left off. It takes the ideas of a decentered self and makes it more concrete by modeling mind as a multiprocessing machine.”
—Sherry Turkle (b. 1948)