Решето Эратосфена на Python по шагам

Простые числа: решето: разбор по шагам

Решето Эратосфена начинает со списка, где все числа считаются простыми, и для каждого простого p вычёркивает его кратные, начиная с p².

Для больших диапазонов это намного быстрее, чем проверять каждое число отдельно.

На что смотреть в пошаговом режиме

• ячейки списка is_prime, которые становятся False;
• с какого числа начинается вычёркивание для каждого p;
• итоговый список простых чисел.

Код примера

n = 30
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
p = 2
while p * p <= n:
    if is_prime[p]:
        for k in range(p * p, n + 1, p):
            is_prime[k] = False
    p += 1
primes = [i for i in range(n + 1) if is_prime[i]]
print(primes)

Код уже в редакторе. Нажмите «По шагам» и листайте шаги кнопкой ▶ или клавишей →. Код можно менять и запускать заново.

Отладчик Python: как пользоваться и частые вопросы