Понимание премьер сито - PullRequest
Новая
       35

Понимание премьер сито

0 голосов
/ 09 марта 2020

Я пытаюсь понять реализацию пользователем Prime Seive Эрастотена; код состоит всего из нескольких строк, но мне трудно понять его: 

def eratos_sieve(n):
  sieve = [True] * n
  for i in range(3,int(n**0.5)+1,2):
      if sieve[i]:
          sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
  return len([2] + [i for i in range(3,n,2) if sieve[i]])

На данный момент я понимаю следующее: мы определяем функцию с параметром n. Начнем с предположения, что n простое. Тогда по какой-то причине у нас есть для l oop с 3 параметрами! И после этого заявления, я просто полностью потерян. Если кто-то может помочь, это было бы здорово!

1 Ответ

1 голос
/ 09 марта 2020

Возможно, приведенные ниже комментарии к коду могут быть вам полезны - я также упростил код там, где мог (и, надеюсь, не нарушил его!): 

def eratos_sieve(n):

    ''' Return the number of primes less than n '''

    # Create an array [True, True, True, ...] of length n
    # i.e. assume all numbers are prime unless proven otherwise
    sieve = [True] * n

    # loop over odd numbers from 3 to sqrt(n)
    for i in range(3, int(n**0.5) + 1, 2):

        if sieve[i]:  # if sieve[i] is still True, i is a prime!
            # Assign elements of sieve from i squared to the
            # end of the array skipping by 2 * i (hit multiples
            # of i but skip the even ones) to False. Since this
            # is an array to array assignment, create an array of
            # [False, False, False, ...] of the correct size:
            sieve[i*i::2*i] = [False] * ((n-i * i-1) // (i*2) + 1)

    # Add up odd elements of sieve (True = 1, False = 0),
    # Add one for '2' which we assumed prime:
    return 1 + sum(sieve[3::2])

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

...