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

Можно найти все простые числа, меньшие n, гораздо быстрее, чем проверять на простоту каждое число от 2 до n. Вместо того чтобы последовательно проверять все числа, мы можем проактивно исключать из списка те, которые точно не являются простыми.

Для начала отметим все числа от 2 до n как «возможно простые». Затем исключим из списка все кратные 2 и пометим число 2 как «однозначно простое». После этого исключим из списка все кратные 3 и пометим 3 как «однозначно простое». 4 мы пропустим, так как оно уже было исключено из списка «возможно простых», когда мы обрабатывали 2. Следующее число, которое нужно будет учитывать, — это 5, и мы исключим все его кратные. 6 пропустим, поскольку уже пометили его как составное при обработке 2. Продолжим так до тех пор, пока не дойдём до n.

Симуляция Решета Эратосфена. Нажмите на числа и попробуйте включить все простые, сделав при этом остальные отключёнными.

Интересные особенности и оптимизации алгоритма

Одно из важных следствий удаления всех кратных простому числу p из списка «возможно простых», начиная с самого маленького (2), а затем постепенно увеличивая проверяемое простое p, в том, что вместо обработки всех кратных 2·p, 3·p, 4·p, 5·p... мы можем сразу начинать с p·p. Ведь кратные p вида 2·p, 3·p, 4·p, 5·p и так далее уже были исключены, когда мы обрабатывали числа 2, 3, 5… Поэтому первым ещё нетронутым кратным будет именно p·p.

Таким образом, начиная обработку p=3, мы можем сразу пропустить 6, так как его исключили, когда работали с числом 2, и приступить к 9. Аналогично, приступая к p=5, начинаем сразу с 25, ведь 10 (10 = 2·5) исключили при обработке числа 2, 15 (15 = 3·5) — при обработке 3, а 20 (20 = 4·5) — тоже при обработке 2.

prime = [True] * n                    # prime[i] = True => i — простое число
prime[0] = prime[1] = False           # 0 и 1 не являются простыми

for i in range(2, n):                 # Цикл от 2 до n
    if prime[i]:                      # если i простое, пометить все кратные i как составные
        for j in range(i * i, n, i):  # начинаем с i * i, так как все кратные i меньше этого уже были помечены ранее
            prime[j] = False

Sieve of Eratosthenes to find all the prime numbers smaller than n.

Давайте проследим этот процесс для n=100:

prime = [False, False, True, True, ..., True] размером 100

i = 2 ⇒ prime[2] = True ⇒ for j in 4, 6, 8, ... 100 и помечаем prime[j]=False

i = 3 ⇒ prime[3] = True ⇒ for j in 9, 12, ... 100 и помечаем prime[j]=False

i = 4 ⇒ prime[4] = False

i = 5 ⇒ prime[5] = True ⇒ for j in 25, 30, ... 100 и помечаем prime[j]=False

i = 6 ⇒ prime[6] = False

i = 7 ⇒ prime[7] = True ⇒ for j in 49, 56, ... 100 и помечаем prime[j]=False

i = 8 ⇒ prime[8] = False

i = 9 ⇒ prime[9] = False

i = 10 ⇒ prime[10] = False

i = 11 ⇒ prime[11] = True ⇒ for j in [empty] и помечаем prime[j]=False

На этом этапе i * i уже больше n. Мы больше не будем помечать какие-либо числа как составные, значит можно пройти по массиву и вывести все простые числа, которые меньше 100.

Такой подход работает значительно быстрее и выполняет операций. Это очень ощутимое улучшение! Выполнение операций вместо даёт колоссальную разницу. Возвращаясь к примеру, где на n операций уходило бы 10 лет (3650 дней), а на — 2 месяца (61 день), при вычисления заняли бы меньше 4 дней!

Ещё одна оптимизация, упомянутая в симуляции, — это ограничить внешний цикл значением . Так как внутренний цикл начинается с i·i, для всех чисел, превышающих корень из n, во внутреннем цикле не будет происходить никаких операций, помечающих их как prime[j] = False.

Ввод

В первой строке входных данных находится одно целое число n (2 ≤ n ≤ ).

Вывод

Программа должна вывести все простые числа, меньшие или равные n.

Примеры

Входные данные	Выходные данные
8	2 3 5 7
17	2 3 5 7 11 13 17
19	2 3 5 7 11 13 17 19

Интересные особенности и оптимизации алгоритма

Ввод

Вывод

Примеры

Constraints

To check your solution you need to sign in

Sign in to continue