Sieve of Eratosthenes · Crible d'Ératosthène
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.
Crible d'Ératosthène
Le mathématicien grec Ératosthène a trouvé les nombres premiers sans diviser quoi que ce soit : écrivez les nombres, puis rayez les multiples de chaque nombre premier.
[True] * (n + 1) crée une liste de n + 1 True valeurs, une pour chaque nombre de 0 à n. Marquer 0 et 1 comme non premiers. Ensuite, pour chaque p encore marqué True, définir tous les multiples de p à partir de p * p sur False. Les nombres encore marqués True à la fin sont les nombres premiers.
Write primes_up_to(n) that returns every prime number from 2 to · à n in order, using the sieve of Eratosthenes. primes_up_to(10) is [2, 3, 5, 7]. · Écrivez primes_up_to(n) qui retourne tous les nombres premiers de 2 à n dans l'ordre, en utilisant le crible d'Ératosthène. primes_up_to(10) est [2, 3, 5, 7].
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.