用“埃氏筛法”求2～100以内的素数。算法原理：2～100以内的数，先去掉2的倍数，再去掉3的倍数，再去掉5的倍数，……依此类推，最后剩下的就是素数。要求使用数组实现。

题目要求使用“埃氏筛法”求2～100以内的素数。算法原理：2～100以内的数，先去除2的倍数，再去除3的倍数、5的倍数、7的倍数……依此类推，不断筛选出新的素数，直至完成。最后剩下的就是素数。要求使用数组实现。

相关问题

用埃氏筛法求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之间的所有素数。

python实现埃氏筛法求2～10000素数

埃氏筛法是一种用于求解一定范围内素数的算法。下面是使用Python实现埃氏筛法求解2～10000的素数的代码：

def sieve_of_eratosthenes(n):
    # 创建一个长度为n+1的列表，用于标记数字是否为素数，初始全部为True
    primes = [True] * (n + 1)
    # 将0和1标记为非素数
    primes[0] = primes[1] = False
    
    p = 2
    while p * p <= n:
        # 如果p没有被标记为非素数，则p一定是素数，因此将p及其倍数标记为非素数
        if primes[p]:
            for i in range(p * p, n + 1, p):
                primes[i] = False
        p += 1
    
    # 返回所有标记为素数的数字
    return [i for i in range(n + 1) if primes[i]]

# 调用函数并打印结果
primes = sieve_of_eratosthenes(10000)
print(primes)

以上代码实现了一个名为`sieve_of_eratosthenes`的函数，该函数接受一个参数`n`，用于指定范围。函数内部使用了一个长度为`n+1`的列表`primes`来标记数字是否为素数，其中初始全部为`True`。然后从2开始，找到一个素数后，将其倍数都标记为非素数。最终，返回所有标记为素数的数字。

在主程序中，调用`sieve_of_eratosthenes`函数并传入10000作为参数，得到2～10000范围内的素数列表，并将其打印输出。