Sieve of Eratosthenes · Crivo 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.
Crivo de Eratóstenes
O matemático grego Eratóstenes encontrou primos sem dividir nada: escreva os números, depois riscue os múltiplos de cada primo.
[True] * (n + 1) cria uma lista de n + 1 True valores, um para cada número de 0 a n. Marque 0 e 1 como não primos. Então, para cada p ainda marcado como True, defina cada múltiplo de p a partir de p * p como False. Os números ainda marcados como True no final são os primos.
Write primes_up_to(n) that returns every prime number from 2 to · até n in order, using the sieve of Eratosthenes. primes_up_to(10) is [2, 3, 5, 7]. · Escreva primes_up_to(n) que retorne todos os números primos de 2 a n em ordem, usando o crivo de Eratóstenes. primes_up_to(10) é [2, 3, 5, 7].
Click Run to see the output here. · Clique em Executar para ver a saída aqui.