社区讨论
qp
P5736【深基7.例2】质数筛参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性，并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mkrtarun
- 此快照首次捕获于
- 2026/01/24 12:30 4 周前
- 此快照最后确认于
- 2026/01/24 12:32 4 周前
题目给了：n < 100
所以可以用O根号n的写法 这种算法可处理个数少但体积大的数
CPPint ch1(int x){//枚举质数
for(int i = 2;i*i<=x;i++){
if(x % i == 0){
return 0;
}
}
return x > 1;// 0,1不是质数
}
在这里明确一个概念： 1、n/1+n/2+n/3+......n/n的时间复杂度是O(n log n) 这种算法可处理个数多但体积小的数，（我用过8e6的）。
CPPconst int N = 1e6 + 10;///枚举因数
int ansp[N];
ansp[0] = 1;// 0,1不是质数
ansp[1] = 1;// 0,1不是质数
for(int i = 2;i<=N;i++){
if(ansp[i] == 0){
for(int j = 2*i;j<=N;j+=i){
ansp[j] = 1;
}
}
}
//时复 O（ n log n)。
这里比较推荐第二种。
回复
共 3 条回复，欢迎继续交流。
正在加载回复...