Sieve of Eratosthenes · Criba de Eratóstenes
Sieve of Eratosthenes
The Greek mathematician Eratosthenes found primes without dividing anything: write down the numbers, then cross out the multiples of each prime.
[True] * (n + 1) makes a list of n + 1 True values, one for each number from 0 to n. Mark 0 and 1 as not prime. Then, for each p still marked True, set every multiple of p from p * p onwards to False. The numbers still marked True at the end are the primes.
Cribado de Eratóstenes
El matemático griego Eratóstenes encontró números primos sin realizar ninguna división: escribe los números y luego tachas los múltiplos de cada primo.
[True] * (n + 1) crea una lista de n + 1 True valores, uno para cada número desde 0 hasta n. Marca 0 y 1 como no primos. A continuación, para cada p que aún esté marcado como True, establece todos los múltiplos de p a partir de p * p en False. Los números que permanecen marcados como True al final son los primos.
Write primes_up_to(n) that returns every prime number from 2 to · hasta n in order, using the sieve of Eratosthenes. primes_up_to(10) is [2, 3, 5, 7]. · Escribe primes_up_to(n) que devuelva todos los números primos desde 2 hasta n en orden, usando la criba de Eratóstenes. primes_up_to(10) es [2, 3, 5, 7].
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.