用埃氏筛法求2～100以内的素数

以下是Python代码实现：

def sieve_of_eratosthenes(n):
    prime = [True] * (n+1)
    prime[0] = prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if prime[i]:
            for j in range(i*i, n+1, i):
                prime[j] = False
    return [i for i in range(n+1) if prime[i]]

primes = sieve_of_eratosthenes(100)
print(primes)

输出结果为：

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

解释一下上述代码的实现：

1. 创建一个长度为n+1的布尔数组prime，用来标记每个数是否为素数。默认设为True。
2. 将0和1标记为False，因为它们不是素数。
3. 从2开始，遍历到$\sqrt{n}$，如果当前数i是素数（即prime[i]为True），则将i的倍数全部标记为False。这里从$i*i$开始是因为小于$i$的倍数已经被之前的数标记过了，不需要再次标记。
4. 最后，遍历整个数组，将所有标记为True的数加入到结果列表中，即为2到n之间的所有素数。