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, analysis and/or computer:
“The spider-mind acquires a faculty of memory, and, with it, a singular skill of analysis and synthesis, taking apart and putting together in different relations the meshes of its trap. Man had in the beginning no power of analysis or synthesis approaching that of the spider, or even of the honey-bee; but he had acute sensibility to the higher forces.”
—Henry Brooks Adams (1838–1918)
“A commodity appears at first sight an extremely obvious, trivial thing. But its analysis brings out that it is a very strange thing, abounding in metaphysical subtleties and theological niceties.”
—Karl Marx (1818–1883)
“Family life is not a computer program that runs on its own; it needs continual input from everyone.”
—Neil Kurshan (20th century)