Sieve of eratosthenes

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Animation of the Eratosthenes breed for minor prime numbers than 120. It includes the optimization of starting with the squares of prime numbers.

The Eratosthenes sieve is an algorithm that allows you to find all the prime numbers smaller than a given natural number. A table is formed with all the natural numbers between 2 and n, and the numbers that are not prime are crossed out as follows: Starting with 2, all its multiples are crossed out; starting again, when an integer is found that has not been crossed out, that number is declared prime, and all its multiples are crossed out, and so on. The process ends when the square of the next confirmed prime number is greater than n.

Sieving process

Let's determine, using the following example, the process to determine the list of prime numbers less than 20.

First step: list the natural numbers between 2 to the number you want, in this case up to 20.

2. Second step: takes the first number not scratched or marked, as a prime number.

3. Third step: all the multiples of the number just indicated as a cousin are tagged.

4. Fourth step: if the square of the first number that has not been scratched or marked is less than 20, then the second step is repeated. If not, the algorithm ends, and all integers are declared cousins.

As 3² = 9 < 20, it goes back to the second step:

In the fourth step, the first number that has not been crossed out or marked is 5. Since its square is greater than 20, the algorithm terminates and all numbers that have not been crossed out are considered prime.

As a result, the prime numbers between 2 and 20 are obtained, and these are: 2, 3, 5, 7, 11, 13, 17, 19.

Refinement

A refinement of the sieve consists of crossing out the multiples of the k-th prime number p_k, starting with p_k² since in the previous steps the multiples of p_k corresponding to all of the above prime numbers, that is, 2p_k, 3p_k, 5p_k,…, to (p_k-1)p_k. The algorithm would terminate when p>²_k>n since there would be nothing what to cross out.

Another refinement consists of generating a list with only odd numbers (since even numbers other than 2 are known not to be prime), and crossing out the multiples of the prime numbers by increments of 2p, that is, the odd multiples (2k+1)p of each prime p. This appears in the original algorithm.

Pseudocode

Algoritmo Criba de Eratóstenes (Complejidad) ${displaystyle O(n~log log n)}$ )
Entry: A natural number $n$ Departure: The set of prime numbers prior to $n$ (including $n$ ) Enter all natural numbers from $2$ until $n$ Stop. $i$ from $2$ until ${displaystyle lfloor {sqrt {n}}rfloor }$ do the following: Yeah. $i$ Not marked. Then: Stop. $j$ from $i$ until ${displaystyle ndiv i}$ do the following: Put a mark on ${displaystyle itimes j}$ The result is: All unmarked numbers

About the notation:

${displaystyle lfloor xrfloor }$ is the whole function part of $x$
${displaystyle adiv b}$ is the quotient to divide $a$ between $b$

For implementation on a computer, a logical type vector is normally managed with $n$ elements. In this way, position $i$ contains the value True as a representation of $i$ has been marked and False in another case.

Euler sieve

A special form of the applied Eratosthenes sieve can be found in Leonhard Euler's proof of the Euler product for the Riemann zeta function, and shows an original way of obtaining such a product, using a modification of the sieve. The Riemann zeta function is represented as

{displaystyle zeta (s)=1+{frac {1}{2^{s}}}+{frac {1}{3^{s}}}+{frac {1}{4^{s}}}+{frac {1}{5^{s}}}+cdots }

Multiplying both members by ${displaystyle textstyle {frac {1}{2^{s}}}}$ a new series is obtained, and by subtracting this new series to the original series member to member and term to term, all the terms whose bases are multiples of 2 — In the Eratosthenes shed are tagged — are deleted.

{displaystyle left(1-{frac {1}{2^{s}}}right)zeta (s)=1+{frac {1}{3^{s}}}+{frac {1}{5^{s}}}+{frac {1}{7^{s}}}+{frac {1}{9^{s}}}+cdots }

Repeating the same process on the following term, ${displaystyle textstyle {frac {1}{3^{s}}}}$ all the terms whose bases are multiples of 3:

{displaystyle left(1-{frac {1}{3^{s}}}right)left(1-{frac {1}{2^{s}}}right)zeta (s)=1+{frac {1}{5^{s}}}+{frac {1}{7^{s}}}+{frac {1}{11^{s}}}+{frac {1}{13^{s}}}+cdots }

It can be verified that the part on the right is being screened, so repeating this process indefinitely:

{displaystyle cdots left(1-{frac {1}{11^{s}}}right)left(1-{frac {1}{7^{s}}}right)left(1-{frac {1}{5^{s}}}right)left(1-{frac {1}{3^{s}}}right)left(1-{frac {1}{2^{s}}}right)zeta (s)=1}

a product is obtained over all the prime numbers p, which can be written in a simplified way as:

{displaystyle zeta (s)=prod _{p}{frac {1}{1-p^{-s}}}.}

Contenido relacionado

Más resultados...