用Python写一个程序,求整数bn以内(包含n)
时间: 2024-05-14 08:12:54 浏览: 73
的所有素数。
可以使用素数筛法,具体步骤如下:
1. 创建一个长度为bn+1的布尔数组,初始值都为True,表示所有数都是素数。
2. 从2开始,遍历到sqrt(bn)为止,如果当前数字i是素数,则从i*i开始,将i的所有倍数标记为非素数(即将对应数组元素赋值为False)。
3. 遍历完毕后,所有数组元素为True的下标即为素数。
代码如下:
```python
import math
def get_primes(bn):
# 创建布尔数组,初始值都为True
primes = [True] * (bn + 1)
primes[0] = primes[1] = False # 0和1不是素数
# 遍历到sqrt(bn)为止
for i in range(2, int(math.sqrt(bn)) + 1):
if primes[i]:
# 将i的所有倍数标记为非素数
for j in range(i * i, bn + 1, i):
primes[j] = False
# 返回所有数组元素为True的下标
return [i for i in range(bn + 1) if primes[i]]
# 测试
print(get_primes(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]
```
阅读全文