Sieve of Eratosthenes
Решето Эратосфена
Греческий математик Эратосфен находил простые числа без деления: запишите все числа, затем зачеркните кратные каждому простому числу.
[True] * (n + 1) создаёт список из n + 1 значений типа True, по одному для каждого числа от 0 до n. Отметьте 0 и 1 как непростые. Затем для каждого p, всё ещё помеченного как True, установите каждое кратное p начиная с p * p в состояние False. Числа, оставшиеся помеченными как True в конце, являются простыми.
Сложность 5/5 · 400 монет + небольшой бонус за первое завершение сегодня
Write primes_up_to(n) that returns every prime number from 2 до n in order, using the sieve of Eratosthenes. primes_up_to(10) является [2, 3, 5, 7].
Нажмите Запустить, чтобы увидеть результат здесь.