Может кто-нибудь помочь мне определить ошибку в основной функции генератора, которую я написал

Question

Может ли кто-нибудь помочь мне, почему я получаю определенные числа, такие как "27" и "35" в моем генераторе, когда я перечисляю первые 25 простых чисел?Я знаю, что есть более эффективные методы, такие как Sieve of Erathosthenes, но меня беспокоит некоторая ошибка в этом коде.Спасибо!

def next_prime():
    num = 2
    while True:
        for i in range(1, num+1):
            if (i != 1) and (num % i == 0):
                # print(num, " is not prime")
                num += 1
        yield num
        num += 1

primes = next_prime()
[print(next(primes)) for i in range(25)]

Вывод ниже - выделены несколько составных чисел

3 5 7 11 13 17 19 23 27 29 31 35 37 41 43 47 53 59 61 67 71 73 79 83 87

Answer 1

Вы увеличиваете num в цикле for, но вы не можете просто сделать это, так как тогда i равно , а не сбрасывается до 1, и, следовательно,Вы пропускаете определенные проверки.

Таким образом, вы должны break, а затем увеличить num и позволить циклу проверить следующий номер.Таким образом, мы можем использовать for - else, чтобы получить число только в том случае, если цикл был успешным (т. Е. Не был достигнут оператор break).

Другая проблема, которая сейчас возникнет, заключается в том, что нет число больше не является простым.Это потому, что ваш range(1, num+1) включает num, а число всегда делится само по себе.Таким образом, диапазон должен составлять от 1 (или лучше 2) до num (эксклюзив):

def next_prime():
    num = 2
    while True:
        for i in range(2, num):
            if num % i == 0:
                break
        else:
            yield num
        num += 1

Однако вышеприведенное не очень эффективно.Мы можем сделать это быстрее.Например, все четные числа, кроме двух, не являются простыми числами, поэтому мы можем переписать это следующим образом:

def next_prime():
    <b>yield 2</b>
    <b>num = 3</b>
    while True:
        for i in range(2, num):
            if not num % i:
                break
        else:
            yield num
        num += <b>2</b>

Кроме того, нам нужно проверить только число √n для числа n, так как если n делится на число a, причем a больше квадратного корня из n, тогда существует число b = n / a, которое меньше квадратного корня:

from math import sqrt, ceil

def next_prime():
    yield 2
    num = 3
    while True:
        for i in range(<b>3</b>, <b>ceil(sqrt(num))+1</b>, 2):
            if not num % i:
                break
        else:
            yield num
        num += 2