Алгоритмы и структуры данных · 14 из 30
Решето Эратосфена
Две тысячи лет назад Эратосфен выписывал числа подряд и вычёркивал кратные: сначала кратные двум, потом трём, потом пяти. Что осталось — простые. Борис Аркадьевич требует именно решето, а не проверку каждого числа делением, — «на миллионе почувствуете разницу».
Что сделать
Найдите решетом Эратосфена все простые числа от 2 до n включительно.
Что приходит
n— целое число, не меньше нуля
Что вернуть
Список простых чисел от 2 до n по возрастанию; если n меньше двух — пустой список.
Допишите функцию resheto в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
resheto(20)
[2, 3, 5, 7, 11, 13, 17, 19]
Заведите список отметок «простое ли» для чисел от 0 до n. Ноль и единица — не простые. Для каждого i от 2, пока i · i ≤ n: если i ещё отмечено простым, вычеркните его кратные, начиная с i · i, с шагом i.
Верните числа, оставшиеся отмеченными, по возрастанию. Само n входит в проверку: при n = 13 ответ кончается на 13.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.