Whereas the sieve of Eratosthenes marks off each non-prime for each of its prime factors, the sieve of Pritchard avoids considering almost all non-prime numbers by building progressively larger wheels, which represent the pattern of numbers not divisible by any of the primes processed thus far. It thereby achieves a better asymptotic complexity, and was the first sieve with a running time sublinear in the specified bound. Its asymptotic running-time has not been improved on, and it deletes fewer composites than any other known sieve. It was created in 1979 by Paul Pritchard.[2]
Since Pritchard has created a number of other sieve algorithms for finding prime numbers,[3][4][5] the sieve of Pritchard is sometimes singled out by being called the wheel sieve (by Pritchard himself[1]) or the dynamic wheel sieve.[6]
To find all the prime numbers less than or equal to a given integer N, a sieve algorithm examines a set of candidates in the range 2, 3, …, N, and eliminates those that are not prime, leaving the primes at the end. The sieve of Eratosthenes examines all of the range, first removing all multiples of the first prime 2, then of the next prime 3, and so on. The sieve of Pritchard instead examines a subset of the range consisting of numbers that occur on successive wheels, which represent the pattern of numbers left after each successive prime is processed by the sieve of Eratosthenes.
For i > 0, the ith wheel Wi represents this pattern. It is the set of numbers between 1 and the product Pi = p1·p2⋯pi of the first i prime numbers that are not divisible by any of these prime numbers (and is said to have an associated lengthPi). This is because adding Pi to a number does not change whether it is divisible by one of the first i prime numbers, since the remainder on division by any one of these primes is unchanged.
So W1 = {1} with length P1 = 2 represents the pattern of odd numbers; W2 = {1,5} with length P2 = 6 represents the pattern of numbers not divisible by 2 or 3; etc. Wheels are so-called because Wi can be usefully visualized as a circle of circumference Pi with its members marked at their corresponding distances from an origin. Then rolling the wheel along the number line marks points corresponding to successive numbers not divisible by one of the first i prime numbers. The animation shows W2 being rolled up to 30.
Rolling the 2nd wheel up to 30.
It is useful to define Wi→n for n > 0 to be the result of rolling Wi up to n. Then the animation generates W2→ 30 = {1,5,7,11,13,17,19,23,25,29}. Note that up to 52− 1 = 24, this consists only of 1 and the primes between 5 and 25.
The sieve of Pritchard is derived from the observation[1] that this holds generally: for all i > 0, the values in Wi→ (p2 i+1− 1) are 1 and the primes between pi+1 and p2 i+1. It even holds for i = 0, where the wheel has length 1 and contains just 1 (representing all the natural numbers). So the sieve of Pritchard starts with the trivial wheel W0 and builds successive wheels until the square of the wheel's first member after 1 is at least N. Wheels grow very quickly, but only their values up to N are needed and generated.
It remains to find a method for generating the next wheel. Note in the animation that W3 = {1,5,7,11,13,17,19,23,25,29} − {5 · 1 , 5 · 5} can be obtained by rolling W2 up to 30 and then removing 5 times each member of W2.This also holds generally: for all i≥ 0, Wi+1 = (Wi→Pi+1) − {pi+1·w | w∈Wi}.[1] Rolling Wi past Pi just adds values to Wi, so the current wheel is first extended by getting each successive member starting with w = 1, adding Pi to it, and inserting the result in the set. Then the multiples of pi+1 are deleted. Care must be taken to avoid a number being deleted that itself needs to be multiplied by pi+1. The sieve of Pritchard as originally presented[2] does so by first skipping past successive members until finding the maximum one needed, and then doing the deletions in reverse order by working back through the set. This is the method used in the first animation above. A simpler approach is just to gather the multiples of pi+1 in a list, and then delete them.[7] Another approach is given by Gries and Misra.[8]
If the main loop terminates with a wheel whose length is less than N, it is extended up to N to generate the remaining primes.
The algorithm, for finding all primes up to N, is therefore as follows:
Start with a set W = {1} and length = 1 representing wheel 0, and prime p = 2.
As long as p2≤N, do the following:
if length < N, then
extend W by repeatedly getting successive members w of W starting with 1 and inserting length + w into W as long as it does not exceed p·length or N;
increase length to the minimum of p·length and N.
repeatedly delete p times each member of W by first finding the largest ≤length and then working backwards.
note the prime p, then set p to the next member of W after 1 (or 3 if p was 2).
if length < N, then extend W to N by repeatedly getting successive members w of W starting with 1 and inserting length + w into W as long as it does not exceed N;
On termination, the rest of the primes up to N are the members of W after 1.
Example
To find all the prime numbers less than or equal to 150, proceed as follows.
Start with wheel 0 with length 1, representing all natural numbers 1, 2, 3...:
1
The first number after 1 for wheel 0 (when rolled) is 2; note it as a prime. Now form wheel 1 with length 2 × 1 = 2 by first extending wheel 0 up to 2 and then deleting 2 times each number in wheel 0, to get:
1 2
The first number after 1 for wheel 1 (when rolled) is 3; note it as a prime. Now form wheel 2 with length 3 × 2 = 6 by first extending wheel 1 up to 6 and then deleting 3 times each number in wheel 1, to get
1 23 5
The first number after 1 for wheel 2 is 5; note it as a prime. Now form wheel 3 with length 5 × 6 = 30 by first extending wheel 2 up to 30 and then deleting 5 times each number in wheel 2 (in reverse order!), to get
1 235 7 11 13 17 19 23 25 29
The first number after 1 for wheel 3 is 7; note it as a prime. Now wheel 4 has length 7 × 30 = 210, so we only extend wheel 3 up to our limit 150. (No further extending will be done now that the limit has been reached.) We then delete 7 times each number in wheel 3 until we exceed our limit 150, to get the elements in wheel 4 up to 150:
The first number after 1 for this partial wheel 4 is 11; note it as a prime. Since we have finished with rolling, we delete 11 times each number in the partial wheel 4 until we exceed our limit 150, to get the elements in wheel 5 up to 150:
The first number after 1 for this partial wheel 5 is 13. Since 13 squared is at least our limit 150, we stop. The remaining numbers (other than 1) are the rest of the primes up to our limit 150.
Just 8 composite numbers are removed, once each. The rest of the numbers considered (other than 1) are prime. In comparison, the natural version of Eratosthenes sieve (stopping at the same point) removes composite numbers 184 times.
Pseudocode
The sieve of Pritchard can be expressed in pseudocode, as follows:[1]
algorithm Sieve of Pritchard isinput: an integer N >= 2. output: the set of prime numbers in {1,2,...,N}. letW and Pr be sets of integer values, and all other variables integer values. k, W, length, p, Pr := 1, {1}, 2, 3, {2}; {invariant: p = pk+1 and W = Wk {1,2,...,N} and length = minimum of Pk,N and Pr = the primes up to pk} whilep2 <= Ndoif (length < N) then Extend W,length to minimum of p*length,N; Delete multiples of p from W; Insert p into Pr; k, p := k+1, next(W, 1) if (length < N) then Extend W,length to N; returnPrW - {1};
where next(W, w) is the next value in the ordered set W after w.
procedure Extend W,length to nis {in:W = Wk and length = Pk and n > length} {out:W = Wkn and length = n} integer w, x; w, x := 1, length+1; whilex <= ndo Insert x into W; w := next(W,w); x := length + w; length := n;
procedure Delete multiples of p from W,lengthisinteger w; w := p; whilep*w <= lengthdow := next(W,w); whilew > 1 dow := prev(W,w); Remove p*w from W;
where prev(W, w) is the previous value in the ordered set W before w. The algorithm can be initialized with W0 instead of W1 at the minor complication of making next(W, 1) a special case when k = 0.
This abstract algorithm uses ordered sets supporting the operations of insertion of a value greater than the maximum, deletion of a member, getting the next value after a member, and getting the previous value before a member. Using one of Mertens' theorems (the third) it can be shown to use O(N / log log N) of these operations and additions and multiplications.[2]
Implementation
An array-based doubly-linked list s can be used to implement the ordered set W, with s[w] storing next(W,w) and s[w-1] storing prev(W,w). This permits each abstract operation to be implemented in a small number of operations. (The array can also be used to store the set Pr "for free".) Therefore the time complexity of the sieve of Pritchard to calculate the primes up to N in the random access machine model is O(N / log log N) operations on words of size O(log N). Pritchard also shows how multiplications can be eliminated by using very small multiplication tables,[2] so the bit complexity is O(N log N / log log N) bit operations.
In the same model, the space complexity is O(N) words, i.e., O(N log N) bits. The sieve of Eratosthenes requires only 1 bit for each candidate in the range 2 through N, so its space complexity is lower at O(N) bits. Note that space needed for the primes is not counted, since they can printed or written to external storage as they are found. Pritchard[2] presented a variant of his sieve that requires only O(N / log log N) bits without compromising the sublinear time complexity, making it asymptotically superior to the natural version of the sieve of Eratostheses in both time and space.
However, the sieve of Eratostheses can be optimized to require much less memory by operating on successive segments of the natural numbers.[9] Its space complexity can be reduced to O(√N) bits without increasing its time complexity.[3] This means that in practice it can be used for much larger limits N than would otherwise fit in memory, and also take advantage of fast cache memory. For maximum speed, it is also optimized using a small wheel to avoid sieving with the first few primes (although this does not change its asymptotic time complexity). Therefore the sieve of Pritchard is not competitive as a practical sieve over sufficiently large ranges.
Geometric model
Generating successive wheels up to
At the heart of the sieve of Pritchard is an algorithm for building successive wheels. It has a simple geometric model as follows:
Start with a circle of circumference 1 with a mark at 1.
To generate the next wheel:
Go around the wheel and find (the distance to) the first mark after 1; call it p.
Create a new circle with p times the circumference of the current wheel.
Roll the current wheel around the new circle, marking it where a mark touches it.
Magnify the current wheel by p and remove the marks that coincide.
For the first 2 iterations it is necessary to continue round the circle until 1 is reached again.
The first circle represents W0 = {1}, and successive circles represent wheels W1, W2, …. The animation on the right shows this model in action up to W3.
It is apparent from the model that wheels are symmetric. This is because Pk−w is not divisible by one of the first k primes if and only if w is not so divisible. It is possible to exploit this to avoid processing some composites, but at the cost of a more complex algorithm.
Related sieves
Once the wheel in the sieve of Pritchard reaches its maximum size, the remaining operations are equivalent to those performed by Euler's sieve.
The sieve of Pritchard is unique in conflating the set of prime candidates with a dynamic wheel used to speed up the sifting process. But a separate static wheel (as frequently used to speed up the sieve of Eratosthenes) can give an O(log log N) speedup to the latter, or to linear sieves, provided it is large enough (as a function of N). Examples are the use of the largest wheel of length not exceeding √N / log2N to get a version of the sieve of Eratosthenes that takes O(N) additions and requires only O(√N / log log N) bits,[3] and the speedup of the naturally linear sieve of Atkin to get a sublinear optimized version.
Bengalloun found a linear smoothly incremental sieve,[10] i.e., one that (in theory) can run indefinitely and takes a bounded number of operations to increment the current bound N. He also showed how to make it sublinear by adapting the sieve of Pritchard to incrementally build the next dynamic wheel while the current one is being used. Pritchard[5] showed how to avoid multiplications, thereby obtaining the same asymptotic bit-complexity as the sieve of Pritchard.
Runciman provides a functional algorithm[11] inspired by the sieve of Pritchard.
In mathematics, the factorial of a non-negative integer , denoted by , is the product of all positive integers less than or equal to . The factorial of also equals the product of with the next smaller factorial: For example, The value of 0! is 1, according to the convention for an empty product.
In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers x, y, the greatest common divisor of x and y is denoted . For example, the GCD of 8 and 12 is 4, that is, gcd(8, 12) = 4.
In mathematics, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is called a composite number, or it is not, in which case it is called a prime number. For example, 15 is a composite number because 15 = 3 · 5, but 7 is a prime number because it cannot be decomposed in this way. If one of the factors is composite, it can in turn be written as a product of smaller factors, for example 60 = 3 · 20 = 3 · (5 · 4). Continuing this process until every factor is prime is called prime factorization; the result is always unique up to the order of the factors by the prime factorization theorem.
A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.
In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.
In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than 10100. Heuristically, its complexity for factoring an integer n (consisting of ⌊log2n⌋ + 1 bits) is of the form
A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy. Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might more accurately be called compositeness tests instead of primality tests.
In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory.
Trial division is the most laborious but easiest to understand of the integer factorization algorithms. The essential idea behind trial division tests to see if an integer n, the integer to be factored, can be divided by each number in turn that is less than the square root of n.
The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second-fastest method known. It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve.
In number theory, a branch of mathematics, the special number field sieve (SNFS) is a special-purpose integer factorization algorithm. The general number field sieve (GNFS) was derived from it.
TWINKLE is a hypothetical integer factorization device described in 1999 by Adi Shamir and purported to be capable of factoring 512-bit integers. It is also a pun on the twinkling LEDs used in the device. Shamir estimated that the cost of TWINKLE could be as low as $5000 per unit with bulk production. TWINKLE has a successor named TWIRL which is more efficient.
In number theory, an n-smooth (or n-friable) number is an integer whose prime factors are all less than or equal to n. For example, a 7-smooth number is a number in which every prime factor is at most 7. Therefore, 49 = 72 and 15750 = 2 × 32 × 53 × 7 are both 7-smooth, while 11 and 702 = 2 × 33 × 13 are not 7-smooth. The term seems to have been coined by Leonard Adleman. Smooth numbers are especially important in cryptography, which relies on factorization of integers. 2-smooth numbers are simply the powers of 2, while 5-smooth numbers are also known as regular numbers.
In mathematics, the Legendre sieve, named after Adrien-Marie Legendre, is the simplest method in modern sieve theory. It applies the concept of the Sieve of Eratosthenes to find upper or lower bounds on the number of primes within a given set of integers. Because it is a simple extension of Eratosthenes' idea, it is sometimes called the Legendre–Eratosthenes sieve.
In mathematics, the sieve of Atkin is a modern algorithm for finding all prime numbers up to a specified integer. Compared with the ancient sieve of Eratosthenes, which marks off multiples of primes, the sieve of Atkin does some preliminary work and then marks off multiples of squares of primes, thus achieving a better theoretical asymptotic complexity. It was created in 2003 by A. O. L. Atkin and Daniel J. Bernstein.
In computational number theory, a variety of algorithms make it possible to generate prime numbers efficiently. These are used in various applications, for example hashing, public-key cryptography, and search of prime factors in large numbers.
In mathematics, the rational sieve is a general algorithm for factoring integers into prime factors. It is a special case of the general number field sieve. While it is less efficient than the general algorithm, it is conceptually simpler. It serves as a helpful first step in understanding how the general number field sieve works.
Wheel factorization is a method for generating a sequence of natural numbers by repeated additions, as determined by a number of the first few primes, so that the generated numbers are coprime with these primes, by construction.
In mathematics, the sieve of Sundaram is a variant of the sieve of Eratosthenes, a simple deterministic algorithm for finding all the prime numbers up to a specified integer. It was discovered by Indian student S. P. Sundaram in 1934.
↑ Bays, Carter; Hudson, Richard H. (1977). "The segmented sieve of Eratosthenes and primes in arithmetic progressions to 1012". BIT. 17 (2): 121–127. doi:10.1007/BF01932283. S2CID122592488.
Italics indicate that algorithm is for numbers of special forms
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
