了解基本筛子

Question

我正在尝试了解用户对Erastothene的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为质数。然后，由于某种原因，我们有一个带3个参数的for循环！在那句话之后，我完全迷失了。如果有人可以帮助，那就太好了！

Answer 1

也许下面的代码注释可能对您有所帮助-我还在可能的地方简化了代码（并希望不会破坏它！）：

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中的元素数量减少一半，而不是存储它忽略的偶数元素。当然，这会使索引编制更加复杂，但可行。