Решето Эратосфена
- Не решено
Напишите функцию sieve
, которая будет возвращать список всех простых чисел меньше заданного n
. Для этого можно воспользоваться решетом Эратосфена.
Алгоритм
Для нахождения всех простых чисел не больше заданного числа n
, следуя методу Эратосфена, нужно выполнить следующие шаги:
- Выписать подряд все целые числа от двух до
n: (2, 3, 4, …, n)
. - Пусть переменная
p
изначально равна2
— первому простому числу. - Зачеркнуть в списке числа от
2p
доn
считая шагами поp
(это будут числа кратныеp: 2p, 3p, 4p, …
). - Найти первое незачёркнутое число в списке, большее чем
p
, и присвоить значению переменнойp
это число. - Повторять шаги
3
и4
, пока возможно. - Теперь все незачёркнутые числа в списке — это все простые числа от
2
доn
.
Важно: Алгоритм нужно вывести в виде списка.