用筛选法求100以内的素数

以下是用筛选法求100以内的素数的代码：

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

print(sieve_of_eratosthenes(100))

输出结果为：[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]

相关问题

用筛选法求100以内素数

以下是Python代码实现：

# 初始化所有数字为素数
is_prime = [True] * 101

# 0和1不是素数
is_prime[0] = is_prime[1] = False

# 从2开始枚举，筛选出素数
for i in range(2, 101):
    # 如果当前数字已经被标记为非素数，则跳过
    if not is_prime[i]:
        continue

    # 枚举当前素数的倍数并标记为非素数
    for j in range(i * 2, 101, i):
        is_prime[j] = False

# 输出所有素数
for i in range(2, 101):
    if is_prime[i]:
        print(i, end=' ')

输出结果为：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

python用筛选法求100以内素数

### 回答1：
筛选法是一种常见的求解素数的方法，可以用Python语言实现。具体步骤如下：

1. 创建一个长度为101的列表，用来存储100以内的数字，列表中的每个元素都初始化为True，表示该数字是素数。

2. 从2开始，依次遍历列表中的每个数字，如果该数字是素数，则将它的倍数标记为False，表示它们不是素数。

3. 遍历完列表后，所有未被标记为False的数字都是素数，将它们输出即可。

下面是Python代码实现：

# 创建一个长度为101的列表，用来存储100以内的数字
is_prime = [True] * 101

# 从2开始，依次遍历列表中的每个数字
for i in range(2, 101):
    # 如果该数字是素数，则将它的倍数标记为False
    if is_prime[i]:
        for j in range(i * 2, 101, i):
            is_prime[j] = False

# 输出所有未被标记为False的数字，即素数
for i in range(2, 101):
    if is_prime[i]:
        print(i, end=' ')

输出结果为：

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

以上就是用Python实现筛选法求100以内素数的方法。

### 回答2：
素数是指只能被 1 和本身整除的数，比如2、3、5、7、11等都是素数。求解素数是算法领域的一个经典问题，本文将介绍如何利用 Python 语言通过筛选法求解 100 以内的素数。

筛选法又称埃氏筛法，因为其思想来源于古希腊数学家埃拉托斯特尼（Eratosthenes）的思想。该算法的基本思想是从小到大枚举所有自然数，对于每个质数，如果其小于等于它的平方根，则遍历该质数的所有倍数，并将它们标记为合数。这样，当遍历完所有小于等于 100 的数后，未被标记的数字即为素数。

下面是用 Python 3.0 实现该算法的代码：

#定义一个列表来储存2到100的所有自然数
num_list = list(range(2,101))
#存放素数的空列表
prime = []

while len(num_list) > 0:
    #弹出列表中第一个数（即最小值）
    p = num_list.pop(0)
    #将弹出的数加入素数列表
    prime.append(p)
    #筛去列表中p的倍数
    for i in num_list:
        if i % p == 0:
            num_list.remove(i)

print(prime)

代码逐行解释：

1. 定义一个列表，该列表包含了 2 到 100 之间的所有自然数

# 定义一个列表来储存2到100的所有自然数
num_list = list(range(2,101))

2. 定义一个空列表，用于储存素数

# 存放素数的空列表
prime = []

3. 使用 while 循环，只要 num_list 列表中还有数，就一直循环

while len(num_list) > 0:

4. 弹出列表中第一个数，即最小值

p = num_list.pop(0)

5. 将弹出的数加入素数列表

prime.append(p)

6. 使用 for 循环，遍历 num_list 中所有数，将 p 的倍数都从 num_list 中删除

for i in num_list:
    if i % p == 0:
        num_list.remove(i)

7. 循环结束后，未被删除的数就是 100 以内的所有素数

print(prime)

总结：Python 语言通过筛选法求解 100 以内的素数非常简单，只需要按照上述步骤编写代码即可。此外，人们常常使用的是厄拉多塞筛法和欧拉筛法，在实际使用中还需要特别注意算法的性能问题，以获取更快的执行速度。

### 回答3：
要用python求出100以内的所有素数，可以使用筛选法，也称为埃氏筛或爱拉托逊斯筛法。

首先，我们可以建立一个长度为101的数组，表示从0到100的数字。数组的每个元素都默认为1，代表这个数字是素数。然后我们从2开始，依次将2的倍数、3的倍数、4的倍数……筛选掉。

具体实现就是，对于每个数字i（i从2到100），如果它是素数（数组中对应元素为1），则把它的所有倍数（除它本身外）都标记为非素数（对应数组元素设为0）。这一步可以用两个循环实现，外层循环遍历2到100，内层循环依次将当前数字i的2倍、3倍、4倍……标记为非素数。

最后，再遍历一遍数组，将所有元素值为1的下标输出即为100以内的素数。

下面是具体实现的python代码：

nums = [1]*101  # 初始化数组，全都默认为素数（1）
for i in range(2, 11):  # 从2到10依次遍历
    if nums[i]:  # 如果当前数字i是素数
        for j in range(2*i, 101, i):  # 将当前数字i的2倍、3倍、4倍……都标记为非素数
            nums[j] = 0

primes = []  # 用列表记录所有素数
for i in range(2, 101):  # 再次遍历数组
    if nums[i]:  # 如果当前数字是素数，将它的下标加入列表
        primes.append(i)

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]

可以看到，输出结果包含了所有100以内的素数。