Алгоритм решета Эратосфена (синтаксис Python) - PullRequest
Новая
       0

Алгоритм решета Эратосфена (синтаксис Python)

2 голосов
/ 10 апреля 2011

Итак, я читал статью в Википедии о Сите Эратосфена, и она включала реализацию Python: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity_and_implementation

def eratosthenes_sieve(n):
    # Create a candidate list within which non-primes will be
    # marked as None; only candidates below sqrt(n) need be checked. 
    candidates = range(n+1)
    fin = int(n**0.5)

    # Loop over the candidates, marking out each multiple.
    for i in xrange(2, fin+1):
        if not candidates[i]:
            continue

        candidates[2*i::i] = [None] * (n//i - 1)

    # Filter out non-primes and return the list.
    return [i for i in candidates[2:] if i]

Это похоже на очень простую и элегантную реализацию.Я видел другие реализации, даже в Python, и я понимаю, как работает Sieve.Но конкретный способ работы этой реализации, я немного запутался. Кажется, кто бы ни писал эту страницу, он был довольно умен.

Я понял, что она перебирает список, находит простые числа, а затем отмечает несколько простых чисел.как не простое число.

Но что именно делает эта строка: 

candidates[2*i::i] = [None] * (n//i - 1)

Я выяснил, что его кандидаты срезаются от 2 * i до конца, итерируя по i, поэтомуэто означает, что все кратные i, начинаются с 2 * i, затем переходят к 3 * i, затем переходят к 4 * i, пока вы не закончите список.

Но что означает [None] * (n//i - 1) Почему бы просто не установитьэто ложно?

Спасибо. Вид конкретного вопроса с одним ответом, но я думаю, что это то место, где его можно задать. Я был бы признателен за четкое объяснение.

Ответы [ 2 ]

3 голосов
/ 10 апреля 2011 
candidates[2*i::i] = [None] * (n//i - 1)

это всего лишь краткий способ написания 

for j in range(2 * i, n, i):
    candidates[j] = None

, который работает путем присвоения списка None с фрагменту candidates.

2 голосов
/ 10 апреля 2011

L * N создает и объединяет N (мелкие) копии L, поэтому [None] * (n//i - 1) дает список ceil(n / i) раз None. Назначение среза (L[start:end:step] = new_L) перезаписывает элементы списка, к которому соприкасается срез, с элементами new_L.

Вы правы, можно было бы также установить элементы на False - я думаю, что это было бы предпочтительнее, автор кода явно думал, что None будет лучшим индикатором "перечеркнутого". Но None работает так же, как bool(None) is False и .. if i по сути if bool(i).

...