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

У меня есть этот код, который я не совсем понимаю, потому что я только начал изучать Python неделю назад.

import numpy as np
import time

start_time=time.clock()

def Sieb(n):                           #Sieve
    Eins = np.ones(n, dtype=bool)      #Eins is just german for One
    Eins[0] = Eins[1] = False          #->I don't quite understand what
    for i in range(2, n):              #this one does.
        if Eins[i]:
            Eins[i*i::i] = False       #Does this make the ones = zero?
    return np.flatnonzero(Eins)


print Sieb(1000000)
print start_time

Итак, я понимаю концепцию сита (наверное), но я не уверен, как это достигается здесь. Где кратные самому себе попадают в 0 и как np.flatnonzero выводит простые числа, потому что до этого они были просто 1 и 0?

Я надеюсь, что вы можете понять и помочь мне. :)


python primes sieve
person Lennox    schedule 12.11.2018    source источник
comment
Eins[0] = Eins[1] = False: потому что 0 и 1 не являются простыми числами.   -  person 9769953    schedule 12.11.2018
comment
if Eins[i]: Eins[i*i::i] = False: если i число равно False (= не простое), установите его квадрат и каждое i-е последующее число как False/не простое. Это часть сита.   -  person 9769953    schedule 12.11.2018
comment
Обратите внимание, что часть просеивания начинается с квадрата, поскольку все варианты ниже этого (2*i, 3*i, ...) уже были отфильтрованы на предыдущем шаге (а именно, для простых чисел 2, 3, 5, .. .).   -  person 9769953    schedule 12.11.2018
comment
Затем, переходя от 2 к n, если Eins[i] не равно нулю (т. е. простое число), мы начинаем с его квадрата и устанавливаем для каждого i-го элемента (т. е. его кратные числа) значение False (т. е. не простое число).   -  person Nitin Pawar    schedule 12.11.2018
comment
flatnontzero правильно задокументирован: он возвращает (сглаженный ) индексы ненулевых (неложных, не простых) чисел. Поскольку мы используем индексы как фактические числа для проверки сита, это дает простые числа.   -  person 9769953    schedule 12.11.2018

Ответы (1)


arrow_upward
2
arrow_downward

Давайте рассмотрим это шаг за шагом.

Eins = np.ones(n, dtype=bool)

Это создает новый массив размером n с типом bool и всеми единицами. Из-за типа «один» означает True. Массив представляет все наши числа, которые мы хотим проверить на простоту, где True означает, что число простое, а False — нет. Итак, мы начинаем со всех чисел, помеченных как (потенциальные) простые числа.

Eins[0] = Eins[1] = False

Теперь мы устанавливаем элементы 0th и 1st равными False: ни 0, ни 1 не являются простыми числами.

for i in range(2, n):

Далее мы перебираем все оставшиеся числа (начиная с 2). Мы могли бы обойтись только поиском квадратного корня из n, но для простоты мы просматриваем все числа.

    if Eins[i]:

Если ith значение массива равно True, это означает, что i является простым числом. В первый раз это условие будет введено с i=2. Затем мы хотим удалить все кратные нашему числу из простых кандидатов:

        Eins[i*i::i] = False

Мы можем прочитать эту строку так, как если бы она была Eins[2*i::i] = False, начиная с i*i — это просто оптимизация¹. Если 2 — простое число, это означает, что 2*2, 3*2, 4*2, ... нет, поэтому мы устанавливаем кратные False. Обозначение индексации означает «от i*i до конца» (представлено пустым пространством между двоеточиями) «с шагом i». Этот оператор производит числа i*i, i*(i+1), i*(i+2), ..., то есть все числа, кратные i, которые еще не помечены как "не простые".

return np.flatnonzero(Eins)

И это просто возвращает все индексы, где значение равно True, то есть все простые числа, которые были найдены.

1: Несколько слов о i*i: Мы можем начать с квадрата i, потому что любые числа j*i (для j < i) уже были помечены как непростые, когда мы были в j.

Вот демонстрация того, что это работает для n=15:

Начнем с массива, заполненного .ones:

 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
[T, T, T, T, T, T, T, T, T, T, T, T, T, T, T]

Затем мы очищаем Eins[0] и Eins[1]:

 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
[F, F, T, T, T, T, T, T, T, T, T, T, T, T, T]

И теперь мы начинаем перебирать диапазон, начиная с i=2, и удаляем все числа, кратные 2, начиная с 2*2=4:

 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
[F, F, T, T, F, T, F, T, F, T, F, T, F, T, F]

i=3, удаляя все числа, кратные 3, начиная с 3*3=9:

 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
[F, F, T, T, F, T, F, T, F, F, F, T, F, T, F]

Обратите внимание, что нам не нужно было удалять 6, потому что он уже был удален i=2.

Когда i=4, мы пропускаем удаление, потому что Eins[i] это False. Начиная с i=5 ничего не происходит, потому что квадраты (25, 36,...) больше, чем массив. Наконец, мы используем flatnonzero и получаем все индексы, где значение равно True:

 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
[F, F, T, T, F, T, F, T, F, F, F, T, F, T, F]
       2  3     5     7          11    13
person L3viathan    schedule 12.11.2018