Понимание сита Эратосфена в Python

Этот код представляет собой попытку использования пробного деления для получения последовательности простых чисел.

Чтобы исправить это:

pp = 2
ps = [pp]
lim = raw_input("Generate prime numbers up to what number? : ")
while pp < int(lim):
    pp += 1
    for a in ps:
        if pp%a==0:
            break
    else:                # unindent
        ps.append(pp)    #  this

Чтобы сделать его намного более эффективным (по сути, оптимальным) пробным делением:

pp = 2
ps = [pp]
lim = raw_input("Generate prime numbers up to what number? : ")
while pp < int(lim):
    pp += 1
    for a in ps:
        if a*a > pp:         # stop
            ps.append(pp)    #  early
            break
        if pp%a==0:
            break

Так как настоящего сита еще никто не показал и не объяснил, попробую.

Основной метод - начать отсчет с 2 и исключить 2 * 2 и все более высокие числа, кратные 2 (например, 4, 6, 8 ...), поскольку ни одно из них не может быть простым. 3 пережил первый раунд, поэтому он прост, и теперь мы исключаем 3 * 3 и все более высокие числа, кратные 3 (то есть 9, 12, 15 ...). 4 было исключено, 5 уцелело и т.д. Возведение в квадрат каждого простого числа - это оптимизация, которая использует тот факт, что все меньшие кратные каждого нового простого числа будут исключены в предыдущих раундах. При подсчете и удалении непростых чисел с помощью этого процесса останутся только простые числа.

Вот очень простая версия, обратите внимание, что она не использует деление по модулю или корни:

def primes(n): # Sieve of Eratosthenes
    prime, sieve = [], set()
    for q in xrange(2, n+1):
        if q not in sieve:
            prime.append(q)
            sieve.update(range(q*q, n+1, q))
    return prime

>>> primes(100)
[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]

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

Вот версия на основе генератора, которая работает быстрее, чем любая другая, которую я нашел, но достигает лимита памяти Python на n = 10 ** 8 на моей машине.

def pgen(n): # Fastest Eratosthenes generator
    yield 2
    sieve = set()
    for q in xrange(3, n+1, 2):
        if q not in sieve:
            yield q
            sieve.update(range(q*q, n+1, q+q))

>>> timeit('n in pgen(n)', setup="from __main__ import pgen; n=10**6", number=10)
5.987867565927445

Вот немного более медленная, но гораздо более эффективная по памяти версия генератора:

def pgen(maxnum): # Sieve of Eratosthenes generator
    yield 2
    np_f = {}
    for q in xrange(3, maxnum+1, 2):
        f = np_f.pop(q, None)
        if f:
            while f != np_f.setdefault(q+f, f):
                q += f
        else:
            yield q
            np = q*q
            if np < maxnum:
                np_f[np] = q+q

>>> timeit('n in pgen(n)', setup="from __main__ import pgen; n=10**6", number=10)
7.420101730225724

>>> list(pgen(10))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Чтобы проверить, является ли число простым, просто выполните:

>>> 539 in pgen(539)
False
>>> 541 in pgen(541)
True

Вот несколько советов о том, как работает эта версия с более эффективным использованием памяти. Он использует dict для хранения только самого минимума информации, следующих непростых чисел (в качестве ключей) вместе с их множителями (в качестве значений). Поскольку каждый непростой ключ находится в dict, он удаляется, а следующий непростой ключ добавляется с тем же значением множителя.

Во-первых, это не сито.

Вот как это работает. pp - это номер, который мы собираемся протестировать. На каждой итерации цикла while мы перебираем все известные простые числа (ps) и проверяем, делят ли они pp. Если одно из них соответствует, pp не является простым числом, и мы переходим к следующему числу. В противном случае мы добавляем pp в список простых чисел, прежде чем двигаться дальше.

Строка pp%a==0 в основном говорит, что "остаток pp при делении на a равен нулю", т.е. a делит pp, а pp не является простым.

Это продолжается до тех пор, пока число, которое мы проверяем, не превысит некоторый установленный нами верхний предел (lim).

[РЕДАКТИРОВАТЬ: это сито]

isPrime = [True for i in range(lim)]
isPrime[0] = False
isPrime[1] = False

for i in range(lim):
    if isPrime[i]:
        for n in range(2*i, lim, i):
            isPrime[n] = False

Это не самое эффективное сито (более эффективные делают что-то в строке for n in range(2*i, lim, i):, но оно будет работать, и isPrime[i] будет истинным, если i является простым.

Вышеупомянутая реализация дает неправильные ответы. Я внес некоторые изменения в код.

Но вот как работает приведенный выше код.

pp = 2
ps = [pp]

Мы знаем, что первое простое число - 2, поэтому мы создаем список, содержащий только число 2.

lim = raw_input("Generate prime numbers up to what number? : ")

Вышеупомянутая строка принимает ввод от пользователя, который дает нам верхний предел генерируемых простых чисел.

while pp < int(lim):    # 1
      pp += 1           # 2
      primeFlag = True  # 3
      for a in ps:      # 4
          if pp%a==0:
             primeFlag = False
          break
      if primeFlag:     # 5
          ps.append(pp)

Пронумерованные строки делают следующее.

1. Запускает цикл до достижения верхнего предела.
2. Увеличивает переменную pp на 1.
3. Устанавливает переменную флага, которая используется для проверки, является ли число простым.
4. Этот цикл for выполняет итерацию по списку простых чисел, хранящемуся в ps, и проверяет, что текущее число pp делится на любое из этих чисел, если да, то число не простое, а primeFlag устанавливается на False, и мы прерываем внутреннего for цикла.
5. Если число не делится ни на одно из предшествующих ему простых чисел, тогда оно должно быть простым, следовательно, переменная primeFlag равна True, а оператор if добавляет к списку ps pp.