Сито Эратосфена Понимание - PullRequest
Новая
       47

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

0 голосов
/ 12 ноября 2018

У меня есть этот код, который я не совсем понимаю, потому что я только начал изучать 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?

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

1 Ответ

0 голосов
/ 12 ноября 2018

Давайте пройдемся по шагам. 

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

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

Eins[0] = Eins[1] = False

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

for i in range(2, n):

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

    if Eins[i]:

Если i -ое значение массиваравен 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, мы пропускаем удаление, потому чтоause Eins[i] is 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
...