Sieve of Pritchard: algorithm steps for primes up to 150
In mathematics, the sieve of Pritchard is an algorithm for finding all prime numbers up to a specified bound.
Like the ancient sieve of Eratosthenes, it has a simple conceptual basis in number theory.[1]
It is especially suited to quick hand computation for small bounds.
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]
^ abPritchard, Paul (1982). "Explaining the Wheel Sieve". Acta Informatica. 17 (4): 477–485. doi:10.1007/BF00264164. S2CID 122592488.
^Pritchard, Paul (1981). "A Sublinear Additive Sieve for Finding Prime Numbers". Communications of the ACM. 24 (1): 18–23. doi:10.1145/358527.358540. S2CID 16526704.
^Pritchard, Paul (1983). "Fast Compact Prime Number Sieves (Among Others)". Journal of Algorithms. 4 (4): 332–344. doi:10.1016/0196-6774(83)90014-7. hdl:1813/6313. S2CID 1068851.
^Pritchard, Paul (1987). "Linear prime-number sieves: A family tree". Science of Computer Programming. 9 (1): 17–35. doi:10.1016/0167-6423(87)90024-4. S2CID 44111749.
^Pritchard, Paul (1980). "On the prime example of programming". Language Design and Programming Methodology. Lecture Notes in Computer Science. Vol. 877. pp. 280–288. CiteSeerX 10.1.1.52.835. doi:10.1007/3-540-09745-7_5. ISBN 978-3-540-09745-7. S2CID 9214019.
^Dunten, Brian; Jones, Julie; Sorenson, Jonathan (1996). "A Space-Efficient Fast Prime Number Sieve". Information Processing Letters. 59 (2): 79–84. CiteSeerX 10.1.1.31.3936. doi:10.1016/0020-0190(96)00099-3. S2CID 9385950.
and 23 Related for: Sieve of Pritchard information
In mathematics, the sieveof Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking...
mathematics, the sieveof Atkin is a modern algorithm for finding all prime numbers up to a specified integer. Compared with the ancient sieveof Eratosthenes...
In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than 10100. Heuristically...
required wheel representations; Pritchard's variation of the linear time complexity sieveof Eratosthenes/wheel sieve takes O ( N 1 / 2 log log N...
In mathematics, the sieveof Sundaram is a variant of the sieveof Eratosthenes, a simple deterministic algorithm for finding all the prime numbers up...
quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second-fastest method known (after the general number field sieve)....
branch of mathematics, the special number field sieve (SNFS) is a special-purpose integer factorization algorithm. The general number field sieve (GNFS)...
completed with a highly optimized implementation of the general number field sieve run on hundreds of machines. No algorithm has been published that can...
However none of them runs in polynomial time (in the number of digits in the size of the group). Baby-step giant-step Function field sieve Index calculus...
giving the Sieveof Eratosthenes. One way to speed up these methods (and all the others mentioned below) is to pre-compute and store a list of all primes...
divide-and-conquer algorithm that reduces the multiplication of two n-digit numbers to three multiplications of n/2-digit numbers and, by repeating this reduction...
onto the sieve (i.e., increasing the number of equations while reducing the number of variables). The third stage searches for a power s of the generator...
algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without...
The Trachtenberg system is a system of rapid mental calculation. The system consists of a number of readily memorized operations that allow one to perform...
up to 655372 = 4,295,098,369. Preparing such a table (usually via the Sieveof Eratosthenes) would only be worthwhile if many numbers were to be tested...
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...
over a modulus. It is useful in computer science, especially in the field of public-key cryptography, where it is used in both Diffie–Hellman key exchange...
from sieve theory to O ~ ( log ( n ) 7.5 ) {\displaystyle {\tilde {O}}(\log(n)^{7.5})} . In 2005, Pomerance and Lenstra demonstrated a variant of AKS...
by p and see whether the congruence holds. If it does not hold for a value of a, then p is composite. This congruence is unlikely to hold for a random a...
root (isqrt) of a non-negative integer n is the non-negative integer m which is the greatest integer less than or equal to the square root of n, isqrt ...
computes, in addition to the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that...
Global Information