Legendre sieve

Last updated April 29, 2021

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.^[1]

Legendre's identity

The central idea of the method is expressed by the following identity, sometimes called the Legendre identity:

S(A,P)=\sum _{a\in A}\sum _{d\mid a;\,d\mid P}\mu (d)=\sum _{d\mid P}\mu (d)|A_{d}|,

where A is a set of integers, P is a product of distinct primes, $\mu$ is the Möbius function, and $A_{d}$ is the set of integers in A divisible by d, and S(A, P) is defined to be:

S(A,P)=|\{n:n\in A,\gcd(n,P)=1\}|

i.e. S(A, P) is the count of numbers in A with no factors common with P.

Note that in the most typical case, A is all integers less than or equal to some real number X, P is the product of all primes less than or equal to some integer z < X, and then the Legendre identity becomes:

{\begin{aligned}S(A,P)={}&\sum _{d\mid P}\mu (d)\left\lfloor {\frac {X}{d}}\right\rfloor \\[6pt]={}&\lfloor X\rfloor -\sum _{p_{1}\leq z}\left\lfloor {\frac {X}{p_{1}}}\right\rfloor +\sum _{p_{1}<p_{2}\leq z}\left\lfloor {\frac {X}{p_{1}p_{2}}}\right\rfloor \\[4pt]&{}-\sum _{p_{1}<p_{2}<p_{3}\leq z}\left\lfloor {\frac {X}{p_{1}p_{2}p_{3}}}\right\rfloor +\cdots +\mu (P)\left\lfloor {\frac {X}{P}}\right\rfloor \end{aligned}}

(where $\lfloor X\rfloor$ denotes the floor function). In this example the fact that the Legendre identity is derived from the Sieve of Eratosthenes is clear: the first term is the number of integers below X, the second term removes the multiples of all primes, the third term adds back the multiples of two primes (which were miscounted by being "crossed out twice"), and so on until all $2^{\pi (z)}$ (where $\pi (z)$ denotes the number of primes below z) combinations of primes have been covered.

Once S(A, P) has been calculated for this special case, it can be used to bound $\pi (X)$ using the expression

S(A,P)\geq \pi (X)-\pi (z)+1,\,

which follows immediately from the definition of S(A, P).

Limitations

The Legendre sieve has a problem with fractional parts of terms accumulating into a large error, which means the sieve only gives very weak bounds in most cases. For this reason it is almost never used in practice, having been superseded by other techniques such as the Brun sieve and Selberg sieve. However, since these more powerful sieves are extensions of the basic ideas of the Legendre sieve, it is useful to first understand how this sieve works.

Related Research Articles

In number theory, an arithmetic, arithmetical, or number-theoretic function is for most authors any function f(n) whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their definition the requirement that an arithmetical function "expresses some arithmetical property of n".

The Möbius function $μ (n)$ is an important multiplicative function in number theory introduced by the German mathematician August Ferdinand Möbius in 1832. It is ubiquitous in elementary and analytic number theory and most often appears as part of its namesake the Möbius inversion formula. Following work of Gian-Carlo Rota in the 1960s, generalizations of the Möbius function were introduced into combinatorics, and are similarly denoted $μ (x)$ .

In mathematics, the classic Möbius inversion formula is a relation between pairs of arithmetic functions, each defined from the other by sums over divisors. It was introduced into number theory in 1832 by August Ferdinand Möbius.

In number theory, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying the rate at which this occurs. The theorem was proved independently by Jacques Hadamard and Charles Jean de la Vallée Poussin in 1896 using ideas introduced by Bernhard Riemann.

Quadratic reciprocity Gives conditions for the solvability of quadratic equations modulo prime numbers

In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard statement is:

In mathematics, a square-free integer (or squarefree integer) is an integer which is divisible by no perfect square 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 = 3². The smallest positive square-free numbers are

Eulers totient function Gives the number of integers relatively prime to its input

In number theory, Euler's totient function counts the positive integers up to a given integer $n$ that are relatively prime to $n$ . It is written using the Greek letter phi as $or, and may also be called Euler's phi function . In other words, it is the number of integers k in the range 1 \leq k \leq n for which the greatest common divisor gcd(n, k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n .$

In mathematics and computer science, the floor function is the function that takes as input a real number $, and gives as output the greatest integer less than or equal to, denoted or . Similarly, the ceiling function maps to the least integer greater than or equal to, denoted or .$

Root of unity Number that has an integer power equal to 1

In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that yields 1 when raised to some positive integer power $n$ . Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory of group characters, and the discrete Fourier transform.

In physical science and mathematics, the Legendre functions $P λ$ , $Q λ$ and associated Legendre functions $P μ λ$ , $Q μ λ$ , and Legendre functions of the second kind, $Q n$ , are all solutions of Legendre's differential equation. The Legendre polynomials and the associated Legendre polynomials are also solutions of the differential equation in special cases, which, by virtue of being polynomials, have a large number of additional properties, mathematical structure, and applications. For these polynomial solutions, see the separate Wikipedia articles.

Prime-counting function Function representing the number of primes less than or equal to a given number

In mathematics, the prime-counting function is the function counting the number of prime numbers less than or equal to some real number x. It is denoted by $π$ (x).

In mathematics, the Farey sequence of order n is the sequence of completely reduced fractions, either between 0 and 1, or without this restriction, which when in lowest terms have denominators less than or equal to n, arranged in order of increasing size.

In number theory, the Mertens function is defined for all positive integers n as

In number theory, the law of quadratic reciprocity, like the Pythagorean theorem, has lent itself to an unusual number of proofs. Several hundred proofs of the law of quadratic reciprocity have been published.

Euclid's theorem is a fundamental statement in number theory that asserts that there are infinitely many prime numbers. It was first proved by Euclid in his work Elements. There are several proofs of the theorem.

In physics and mathematics, the solid harmonics are solutions of the Laplace equation in spherical polar coordinates, assumed to be (smooth) functions $. There are two kinds: the regular solid harmonics, which vanish at the origin and the irregular solid harmonics, which are singular at the origin. Both sets of functions play an important role in potential theory, and are obtained by rescaling spherical harmonics appropriately:$

In mathematics, the ATS theorem is the theorem on the approximation of a trigonometric sum by a shorter one. The application of the ATS theorem in certain problems of mathematical and theoretical physics can be very helpful.

The Meissel–Lehmer algorithm is an algorithm that computes the prime-counting function.

In number theory, the prime omega functions $and count the number of prime factors of a natural number Thereby counts each distinct prime factor, whereas the related function counts the total number of prime factors of honoring their multiplicity. For example, if we have a prime factorization of of the form for distinct primes, then the respective prime omega functions are given by and . These prime factor counting functions have many important number theoretic relations.$

The purpose of this page is to catalog new, interesting, and useful identities related to number-theoretic divisor sums, i.e., sums of an arithmetic function over the divisors of a natural number $, or equivalently the Dirichlet convolution of an arithmetic function with one:$

References

↑ Iwaniec, Henryk. The sieve of Eratosthenes–Legendre. Annali della Scuola Normale Superiore di Pisa – Classe di Scienze, Sér. 4, 4 no. 2 (1977), pp. 257–268 MR 453676

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.

[1] Iwaniec, Henryk. The sieve of Eratosthenes–Legendre. Annali della Scuola Normale Superiore di Pisa – Classe di Scienze, Sér. 4, 4 no. 2 (1977), pp. 257–268 MR 453676

[1]

Legendre sieve

Contents

Legendre's identity

Limitations

Related Research Articles

References