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. [1] [2]
Start with a list of the integers from 1 to n. From this list, remove all numbers of the form i + j + 2ij where:
The remaining numbers are doubled and incremented by one, giving a list of the odd prime numbers (i.e., all primes except 2) below 2n + 2.
The sieve of Sundaram sieves out the composite numbers just as the sieve of Eratosthenes does, but even numbers are not considered; the work of "crossing out" the multiples of 2 is done by the final double-and-increment step. Whenever Eratosthenes' method would cross out k different multiples of a prime , Sundaram's method crosses out for .
If we start with integers from 1 to n, the final list contains only odd integers from 3 to . From this final list, some odd integers have been excluded; we must show these are precisely the composite odd integers less than .
Let q be an odd integer of the form . Then, q is excluded if and only if k is of the form , that is . Then we have:
So, an odd integer is excluded from the final list if and only if it has a factorization of the form — which is to say, if it has a non-trivial odd factor. Therefore the list must be composed of exactly the set of odd prime numbers less than or equal to .
defsieve_of_Sundaram(n):"""The sieve of Sundaram is a simple deterministic algorithm for finding all the prime numbers up to a specified integer."""k=(n-2)//2integers_list=[True]*(k+1)foriinrange(1,k+1):j=iwhilei+j+2*i*j<=k:integers_list[i+j+2*i*j]=Falsej+=1ifn>2:print(2,end=' ')foriinrange(1,k+1):ifintegers_list[i]:print(2*i+1,end=' ')
The above obscure but as commonly implemented Python version of the Sieve of Sundaram hides the true complexity of the algorithm due to the following reasons:
The following Python code in the same style resolves the above three issues, as well converting the code to a prime counting function that also displays the total number of composite culling representation culling operations:
importmathdefsieve_of_Sundaram(n):"""The sieve of Sundaram is a simple deterministic algorithm for finding all the prime numbers up to a specified integer."""ifn<3:ifn<2:return0else:return1k=(n-3)//2+1integers_list=[Trueforiinrange(k)]ops=0foriinrange((int(math.sqrt(n))-3)//2+1):# if integers_list[i]: # adding this condition turns it into a SoE!p=2*i+3s=(p*p-3)//2# compute cull startforjinrange(s,k,p):integers_list[j]=Falseops+=1print("Total operations: ",ops,";",sep='')count=1foriinrange(k):ifintegers_list[i]:count+=1print("Found ",count," primes to ",n,".",sep='')
Note the commented out line which is all that is necessary to convert the Sieve of Sundaram to the Odds-Only (wheel factorized by the only even prime of two) Sieve of Eratosthenes; this clarifies that the only difference between these two algorithms is that the Sieve of Sundaram culls composite numbers using all odd numbers as the base values, whereas the Odds-Only Sieve of Eratosthenes uses only the odd primes as base values, with both ranges of base values bounded to the square root of the range.
When run for various ranges, it is immediately clear that while, of course, the resulting count of primes for a given range is identical between the two algorithms, the number of culling operations is much higher for the Sieve of Sundaram and also grows much more quickly with increasing range.
From the above implementation, it is clear that the amount of work done is according to the following:
or where:
- the a to b range actually starts at the square of the odd base values, but this difference is negligible for large ranges.
As the integral of the reciprocal of x is exactly , and as the lower value for a is relatively very small (close to one which has a log value of zero), this is about as follows:
or or .
Ignoring the constant factor of one eighth, the asymptotic complexity in Big O notation is clearly .
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:
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.
The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter ζ (zeta), is a mathematical function of a complex variable defined as
In mathematics, a square-free integer (or squarefree integer) is an integer which is divisible by no square number other than 1. That is, its prime factorization has exactly one factor for each prime that appears in it. For example, 10 = 2 ⋅ 5 is square-free, but 18 = 2 ⋅ 3 ⋅ 3 is not, because 18 is divisible by 9 = 32. The smallest positive square-free numbers are
Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical algorithms. On the other hand, factoring numbers of practical significance requires far more qubits than available in the near future. Another concern is that noise in quantum circuits may undermine results, requiring additional qubits for quantum error correction.
In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.
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 mathematics, summation is the addition of a sequence of numbers, called addends or summands; the result is their sum or total. Beside numbers, other types of values can be summed as well: functions, vectors, matrices, polynomials and, in general, elements of any type of mathematical objects on which an operation denoted "+" is defined.
The sum of the reciprocals of all prime numbers diverges; that is:
In mathematics, Bertrand's postulate states that for each there is a prime such that . First conjectured in 1845 by Joseph Bertrand, it was first proven by Chebyshev, and a shorter but also advanced proof was given by Ramanujan.
In number theory, the Mertens function is defined for all positive integers n as
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.
In analytic number theory, Mertens' theorems are three 1874 results related to the density of prime numbers proved by Franz Mertens.
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 whose every prime factor is at most 7, so 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. The 2-smooth numbers are just the powers of 2, while 5-smooth numbers are known as regular numbers.
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.
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 number theory, the parity problem refers to a limitation in sieve theory that prevents sieves from giving good estimates in many kinds of prime-counting problems. The problem was identified and named by Atle Selberg in 1949. Beginning around 1996, John Friedlander and Henryk Iwaniec developed some parity-sensitive sieves that make the parity problem less of an obstacle.
The Meissel–Lehmer algorithm is an algorithm that computes exact values of the prime-counting function.
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. It is especially suited to quick hand computation for small bounds.