Алгоритм вычисления простых чисел в интервале не работает
Я пытаюсь придумать алгоритм, который может найти все простые числа от начального до конечного числа, не начиная с 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 как простое число.
Что я сделал не так?
@mkrieger1 mkrieger1 Хотя это выглядит так, на самом деле он устанавливает i в последний индекс, чтобы второй цикл мог начаться там.
Помимо кода, это отличный вопрос с точки зрения воспроизводимых шагов, результатов (фактических и ожидаемых) и т. д. Добро пожаловать в S.O.!
Ответы 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]
Спасибо за отзыв и умное решение. Я соответствующим образом изменю свой код. :)
Какова цель первого цикла в функции
m? У меня такое впечатление, что ничего не делает.