了解素筛

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 循环！在那个 if 语句之后，我完全迷路了。如果有人能提供帮助，那就太好了！

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

了解素筛

Understanding Prime Sieve

python

primes

sieve