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:
“Cubism had been an analysis of the object and an attempt to put it before us in its totality; both as analysis and as synthesis, it was a criticism of appearance. Surrealism transmuted the object, and suddenly a canvas became an apparition: a new figuration, a real transfiguration.”
—Octavio Paz (b. 1914)
“Ask anyone committed to Marxist analysis how many angels on the head of a pin, and you will be asked in return to never mind the angels, tell me who controls the production of pins.”
—Joan Didion (b. 1934)
“The analogy between the mind and a computer fails for many reasons. The brain is constructed by principles that assure diversity and degeneracy. Unlike a computer, it has no replicative memory. It is historical and value driven. It forms categories by internal criteria and by constraints acting at many scales, not by means of a syntactically constructed program. The world with which the brain interacts is not unequivocally made up of classical categories.”
—Gerald M. Edelman (b. 1928)