用筛法求质数。在2~100的数中,先去掉2的倍数(不包括2),再去掉3的倍数(不包括3),再去掉4的倍数,类似的直到100,则剩下的数都是质数。试用python求出2~100之间的所有质数。提示:可以用列表元素的值0或1表示是否“去掉”,如a[12]=1表示12被“去掉”。
时间: 2023-08-31 12:40:10 浏览: 165
### 回答1:
以下是Python代码实现:
a = [1]*99 # 初始全部标记为1,表示未被去掉
a[0] = 0 # 将1标记为已去掉
for i in range(2, 11):
if a[i-2] == 1: # a[i-2]表示i是否被去掉,因为在列表中i-2为下标
for j in range(i*2, 101, i):
a[j-2] = 0 # 将i的倍数去掉
for i in range(2, 101):
if a[i-2] == 1:
print(i, end=' ') # 输出剩下的质数,注意end=' '表示末尾不换行
### 回答2:
可以通过以下的Python代码使用筛法求解2~100之间的所有质数:
```python
# 初始化列表,其中所有数都认为是质数
is_prime = [1] * 101
# 对2进行筛除
for i in range(2, 101):
if i != 2:
is_prime[i] = 0
# 对当前素数的倍数进行筛除
if is_prime[i] == 1:
for j in range(i*2, 101, i):
is_prime[j] = 0
# 输出所有质数
prime_numbers = []
for i in range(2, 101):
if is_prime[i] == 1:
prime_numbers.append(i)
print(prime_numbers)
```
运行上述代码,会输出2~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]。
该代码首先创建了长度为101的列表is_prime,用于标记2~100之间的数是否为质数。接着对2进行了筛除,即将2的倍数标记为非质数。然后,对当前素数的倍数进行筛除,将所有倍数标记为非质数。最后,遍历is_prime列表,将标记为质数的数加入prime_numbers列表中,并输出结果。
### 回答3:
筛法求质数是一种通过不断排除合数(非质数)的方法来确定质数的算法。根据题目的要求,我们可以使用Python编写以下代码来求解2~100之间的所有质数:
```python
def sieve_of_eratosthenes(n):
primes = [1] * (n+1) # 初始化列表,假设所有数都是质数
primes[0] = primes[1] = 0 # 0和1不是质数
for i in range(2, int(n**0.5)+1):
if primes[i] == 1:
for j in range(i*i, n+1, i):
primes[j] = 0 # 将i的倍数标记为合数
result = [num for num, is_prime in enumerate(primes) if is_prime == 1]
return result
primes = sieve_of_eratosthenes(100)
print(primes)
```
在上面的代码中,我们首先创建一个长度为n+1的列表`primes`,并将列表中所有元素初始化为1,表示所有数都是质数。然后,我们通过遍历2到n的平方根之间的所有数,如果某个数为质数,则将其所有倍数标记为合数(将元素值置为0)。最终返回值为列表中值为1的索引位置,即为2~n之间的所有质数。
运行上述代码,将会得到2~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]。