Скрипт на Python для решета Эратосфена: выводит составные числа

На чтение 3 мин Опубликовано 16.09.2024

Я пишу программу на Python (3.10), которая считает все простые числа и добавляет их в список (уже содержащий 2), и каким-то образом эта программа выводит 16 и 50 в списке (оба делятся на 2, поэтому не являются простыми числами), а также некоторые другие менее заметные составные числа (27, 35, 65).

i = 3 
primes= [2] 
while len(primes)< 25:
    for x in range(len(primes)):
        if i%primes[x] == 0 : 
            i+= 1
            continue
    primes.append(i)
    i+=1

print(primes)

При выполнении программы выводится:

[2, 3, 5, 7, 11, 13, 16, 17, 19, 23, 27, 29, 31, 35, 37, 41, 43, 47, 50, 53, 59, 61, 65, 67, 71]

Где должен выводиться:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Я не пробовал много чего другого.

Оператор continue пропускает к следующей итерации цикла for, а не while, так что когда он проверяет 15, он находит 5 как делитель и пропускает его, затем переходит к 16 и проверяет с следующего простого числа, которое 7 и так далее.

Содержание

Ответ
Объяснение изменений:
Ожидаемый вывод:

Ответ

Конечно! Проблема вашего кода заключается в том, что, когда вы находите, что текущее число делится на какое-либо из найденных простых чисел, вы пропускаете его и переходите к следующему числу i, не проверяя это число полностью. Это происходит потому, что оператор continue внутри вашего цикла for переходит к следующей итерации, но не Breaking the while loop itself, что приводит к тому, что вы добавляете непростые числа в список primes.

Ниже приведен исправленный код, который правильно реализует алгоритм筛选 (Sieve of Eratosthenes) и добавляет только простые числа в список:

i = 3
primes = [2]

while len(primes) < 25:
    is_prime = True  # Предполагаем, что i простое число
    for x in primes:  # Проверяем делимость на уже найденные простые числа
        if x * x > i:  # Если квадрат простого числа больше i, выходим из цикла
            break
        if i % x == 0:  # Если i делится на x, то оно не простое
            is_prime = False
            break

    if is_prime:  # Если is_prime остался True, добавляем число в список
        primes.append(i)

    i += 1  # Переход к следующему числу

print(primes)

Объяснение изменений:

Флаг is_prime: Мы используем переменную is_prime, чтобы отслеживать, является ли текущее число i простым. Если мы находим делитель, мы устанавливаем его в False.
Разбивка цикла: Внутренний цикл for прерывается, если квадрат текущего простого числа больше i. Это улучшает производительность при проверке делимости, поскольку достаточно проверять до квадратного корня из i.
Добавление числа: Мы добавляем число i в список primes только после завершения проверки и если is_prime остался True.

Ожидаемый вывод:

После исправлений программа должна выводить правильный список простых чисел:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

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