Crible d'Ératosthène
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.
Difficulté 5/5 · 400 pièces + un petit bonus lors de la première réussite aujourd'hui
É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].
Cliquez sur Exécuter pour voir le résultat ici.