埃氏筛法求质数
程序员文章站
2024-03-08 23:10:58
...
复杂度仅有O(nlognlogn)的埃氏筛法:
C语言代码:
#include<stdio.h>
int main(void){
int a[10001];
int i,j;
for(i=1;i<=10000;i++){
a[i] = 0;
}
a[0] = a[1] = 1;
for(i=2;i<=10000;i++){
if(a[i] == 0){
for(j=2*i;j<=10000;j+=i){
a[j] = 1;
}
}
}
for(i=0;i<=10000;i++){
if(a[i] == 0){
printf("%d ",i);
}
}
}
运行结果: