用筛选法求100以内的素数
时间: 2023-05-18 21:03:57 浏览: 56
以下是用筛选法求100以内的素数的代码:
```python
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代码实现:
```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代码实现:
```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 实现该算法的代码:
```python
#定义一个列表来储存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 之间的所有自然数
```python
# 定义一个列表来储存2到100的所有自然数
num_list = list(range(2,101))
```
2. 定义一个空列表,用于储存素数
```python
# 存放素数的空列表
prime = []
```
3. 使用 while 循环,只要 num_list 列表中还有数,就一直循环
```python
while len(num_list) > 0:
```
4. 弹出列表中第一个数,即最小值
```python
p = num_list.pop(0)
```
5. 将弹出的数加入素数列表
```python
prime.append(p)
```
6. 使用 for 循环,遍历 num_list 中所有数,将 p 的倍数都从 num_list 中删除
```python
for i in num_list:
if i % p == 0:
num_list.remove(i)
```
7. 循环结束后,未被删除的数就是 100 以内的所有素数
```python
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以内的素数。
阅读全文