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:
“Whatever else American thinkers do, they psychologize, often brilliantly. The trouble is that psychology only takes us so far. The new interest in families has its merits, but it will have done us all a disservice if it turns us away from public issues to private matters. A vision of things that has no room for the inner life is bankrupt, but a psychology without social analysis or politics is both powerless and very lonely.”
—Joseph Featherstone (20th century)
“What, then, is the basic difference between today’s computer and an intelligent being? It is that the computer can be made to see but not to perceive. What matters here is not that the computer is without consciousness but that thus far it is incapable of the spontaneous grasp of pattern—a capacity essential to perception and intelligence.”
—Rudolf Arnheim (b. 1904)