了解埃拉托色尼筛法

Question

我目前正在研究我们在某个 class 中学到的所有算法，试图了解每个算法的作用和方式。但是，我对埃拉托色尼筛中的某条线有点一无所知：

def sieve(n):
    primes = []                           # list
    is_prime = [False,False]+[True]*(n-1) # how does a list [false,false,true,true....] do anything?
    
    for p in range(2,n+1):                #number from 2 to n
        if is_prime[p]:                   #how does this same list finds out if it is a prime number?
            primes.append(p)              # adds p the list
            for i in range(p**2,n+1,p):   # goes from the square of p to n, in p long steps
                is_prime[i]=False         # those found obviously aren't prime
    
    print(primes)                         # prints the list

这是一个非常简单的算法，它的基函数作用于我不理解的东西，所以这有点问题。请哪位大侠解释一下，谢谢。

Answer 1

所以，这个筛子的工作原理是假设所有数字都是质数。这就是 is_prime 列表的用途。这是一个列表，每个数字都有一个布尔值 (False/True)，首先，所有大于 1 的数字都被认为是素数。

当我们逐一检查数字时，我们可以检查该数字之前是否已被丢弃。如果没有，那么我们将它添加到质数中并开始丢弃它的所有倍数。

示例：假设我们运行 sieve(6)。然后is_primes被初始化为[False, False, True, True, True, True, True]。请注意此处的索引如何与每个数字相对应。前两个假数字代表0和1。

在第一次迭代中，我们检查数字 2，发现 is_prime[2] 为 True。所以我们将 2 加到质数上并丢弃所有 2 的倍数，这样列表就变成了 [False, False, True, True, False, True, False].

到达3，我们做同样的事情，在将其添加到素数列表后丢弃所有3的倍数，在4处我们看到该数字已被丢弃（is_primes[4]为False），所以什么都不做。

这种情况会一直持续下去。

了解埃拉托色尼筛法

Understanding the sieve of Eratosthenes

python

python-3.x

list

sieve