Напишите функцию sieve, которая будет возвращать список всех простых чисел меньше заданного n. Для этого можно воспользоваться решетом Эратосфена.

Алгоритм

Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

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

Важно: Алгоритм нужно вывести в виде списка.

Решето Эратосфена

Оформите Premium