专栏文章

本人发现的一个奇奇怪怪的质数筛法

算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip9hz0i
此快照首次捕获于
2025/12/03 08:21
3 个月前
此快照最后确认于
2025/12/03 08:21
3 个月前
查看原文
C
#include<bits/stdc++.h>
using namespace std;
vector<int> isprime(1,1);
int n;
bool pd(int x){
	for(int i=0;i<isprime.size()&&isprime[i]*isprime[i]<=x;i++){
		if(x%isprime[i]==0){
			return 0;
		}
	}
	return 1;
}
int main()
{
	cin>>n;
	isprime[0]=2;
	cout<<2<<' ';
	for(int i=3;i<=n;i++){
		if(pd(i)){
			isprime.push_back(i);
			cout<<i<<' ';
		}
	}
	return 0;
}
时间:O(  $ n \sqrt{n} $  )
空间:O(k)

评论

0 条评论,欢迎与作者交流。

正在加载评论...