Алгоритм вычисления простых чисел в интервале не работает

Я пытаюсь придумать алгоритм, который может найти все простые числа от начального до конечного числа, не начиная с 2 и используя решето Эратосфена для вычисления всех простых чисел до конечного числа и вырезая нужный мне интервал. И не перебирать каждое число в интервале.

Я изменил существующую запись Решета Эратосфена в Python. Это то, что я получил до сих пор:

def m(n: int, l: list):
    for i, v in enumerate(l):
        if v % n == 0 and v != n and v != False:
            break
    for v in range(i, len(l), n):
        l[v] = False
    return l

Эта функция может установить все обычные умножения числа n в массиве l на false, используя тот же принцип, что и решето Эратосфена при маркировке непростых чисел. Вот как вызывается функция:

l = list(range(10, 20))
for i in range(2, 20):
    m(i, l)
print(l)

В этой конфигурации программа вычисляет все простые числа от 10 до (исключая) 20.

Вывод выглядит следующим образом:

[False, 11, False, 13, False, False, False, 17, False, False]

Но это должно выглядеть так:

[False, 11, False, 13, False, False, False, 17, False, 19]

Кажется, что последнее простое число массива игнорируется. Когда я попытался вычислить от 10 до (исключено) 21, он обнаружил 19 как простое число.

Что я сделал не так?

Какова цель первого цикла в функции m? У меня такое впечатление, что ничего не делает.

mkrieger1 16.05.2022 22:55

@mkrieger1 mkrieger1 Хотя это выглядит так, на самом деле он устанавливает i в последний индекс, чтобы второй цикл мог начаться там.

JacobIRR 16.05.2022 23:01

Помимо кода, это отличный вопрос с точки зрения воспроизводимых шагов, результатов (фактических и ожидаемых) и т. д. Добро пожаловать в S.O.!

JacobIRR 16.05.2022 23:09
Как отлаживать небольшие программы. Если вы пройдёте свой код в отладчик, вы сможете увидеть, как каждая строка влияет на ваши переменные, и сузить круг причин проблемы.
Pranav Hosangadi 16.05.2022 23:11
Анализ настроения постов в Twitter с помощью Python, Tweepy и Flair
Анализ настроения постов в Twitter с помощью Python, Tweepy и Flair
Анализ настроения текстовых сообщений может быть настолько сложным или простым, насколько вы его сделаете. Как и в любом ML-проекте, вы можете выбрать...
7 лайфхаков для начинающих Python-программистов
7 лайфхаков для начинающих Python-программистов
В этой статье мы расскажем о хитростях и советах по Python, которые должны быть известны разработчику Python.
Установка Apache Cassandra на Mac OS
Установка Apache Cassandra на Mac OS
Это краткое руководство по установке Apache Cassandra.
Сертификатная программа "Кванты Python": Бэктестер ансамблевых методов на основе ООП
Сертификатная программа "Кванты Python": Бэктестер ансамблевых методов на основе ООП
В одном из недавних постов я рассказал о том, как я использую навыки количественных исследований, которые я совершенствую в рамках программы TPQ...
Создание персонального файлового хранилища
Создание персонального файлового хранилища
Вы когда-нибудь хотели поделиться с кем-то файлом, но он содержал конфиденциальную информацию? Многие думают, что электронная почта безопасна, но это...
Создание приборной панели для анализа данных на GCP - часть I
Создание приборной панели для анализа данных на GCP - часть I
Недавно я столкнулся с интересной бизнес-задачей - визуализацией сбоев в цепочке поставок лекарств, которую могут просматривать врачи и...
2
4
41
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Для вашего конкретного случая использования значение 19 было перезаписано значением False. Я добавил небольшую резервную/проверку работоспособности перед началом второго цикла. Вы можете увидеть, что происходит, в моих логах print:

def m(n: int, l: list):
    # set i to its max value
    broke_out = False
    for i, v in enumerate(l):
        if v % n == 0 and v != n and v != False:
            print(f"breaking on index :{i}")
            broke_out = True
            break
    # SANITY CHECK: if we never broke out of the above loop and we're on the last index, we're done.
    if not broke_out and i == len(l)-1:
        return l
    # now use i as the starting point in this loop
    for x in range(i, len(l), n):
        # if not isinstance(x, int):
        print(f"about to overwrite l[x] which is: {l[x]} where x is: {x}")
        # if l[x] % n == 0:
        l[x] = False
    print(f"State of l before returning : {l}")
    return l

l = list(range(10, 20))

for i in range(2, 20):
    m(i, l)

print(l)

Полный вывод:

breaking on index :0
about to overwrite l[x] which is: 10 where x is: 0
about to overwrite l[x] which is: 12 where x is: 2
about to overwrite l[x] which is: 14 where x is: 4
about to overwrite l[x] which is: 16 where x is: 6
about to overwrite l[x] which is: 18 where x is: 8
State of l before returning : [False, 11, False, 13, False, 15, False, 17, False, 19]
breaking on index :5
about to overwrite l[x] which is: 15 where x is: 5
about to overwrite l[x] which is: False where x is: 8
State of l before returning : [False, 11, False, 13, False, False, False, 17, False, 19]
[False, 11, False, 13, False, False, False, 17, False, 19]
[Finished in 0.1s]

Спасибо за отзыв и умное решение. Я соответствующим образом изменю свой код. :)

ullispc 17.05.2022 20:11

Другие вопросы по теме