python编写一个能使用爱拉托斯散筛法求N以内的素数的程序。
时间: 2024-03-06 11:49:21 浏览: 28
好的,我可以帮你编写一个能使用爱拉托斯散筛法求N以内的素数的Python程序。以下是代码:
```python
def eratosthenes(n):
# 创建一个长度为n+1的列表,用于标记数字是否为素数
prime = [True for i in range(n+1)]
p = 2
while p**2 <= n:
if prime[p]:
# 将p的倍数标记为合数
for i in range(p**2, n+1, p):
prime[i] = False
p += 1
# 输出所有素数
for p in range(2, n+1):
if prime[p]:
print(p, end=' ')
# 测试
n = int(input("请输入一个正整数n:"))
eratosthenes(n)
```
运行程序后,会要求你输入一个正整数n,然后程序会输出1到n之间的所有素数。这个程序的时间复杂度是O(nloglogn),比较高效。
相关问题
爱拉托斯散筛法c++
爱拉托斯特尼筛法(Sieve of Eratosthenes)是一种简单且古老的筛法,用于找出一定范围内的所有质数。以下是C++实现的爱拉托斯特尼筛法代码:
```c++
#include <iostream>
using namespace std;
const int m = 100;
int main() {
int a[m], n = 0;
bool b[m];
// 初始化
for (int i = 0; i < m; i++) {
b[i] = true;
}
// 筛法
for (int i = 2; i < m; i++) {
if (b[i]) {
a[n] = i;
n++;
for (int j = i * i; j < m; j += i) {
b[j] = false;
}
}
}
// 输出
cout << n << endl;
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
return 0;
}
```
该代码使用了一个布尔数组b[m]来表示每个数是否为质数,初始时所有数都被标记为true。然后从2开始遍历数组,如果当前数为质数,则将其加入到结果数组a中,并将其倍数在布尔数组中标记为false。最后输出结果数组即可。