Legendre sieve
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.
The central idea of the method is expressed by the following identity, sometimes called the Legendre identity:
where A is a set of integers, P is a product of distinct primes, is the Möbius function, and is the set of integers in A divisible by d, and S(A, P) is defined to be:
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:
...
Wikipedia