筛选法求素数
程序员文章站
2024-03-15 15:20:42
...
原理:大于 1 的任意一个自然数的倍数(大于1)一定不是素数;从2开始升序遍历,找到一个素数就将它的倍数标记为合数,当一个数是合数时它的倍数已经被标记过,可以直接跳过;
#include<stdio.h>
#define SIZE_N 1000
int prime[SIZE_N];
int main()
{
int i,j,temp;
for(i=0;i<SIZE_N;i++) prime[i]=1;
prime[0]=0;
prime[1]=0;
for(i=2;i<SIZE_N;i++){
if(prime[i]==1){
for(j=2;j<SIZE_N;j++){
temp=i*j;
if(temp>SIZE_N) break;
prime[temp]=0;
}
}
}
for(i=0;i<SIZE_N;i++){
if(prime[i])
printf("%d\t",i);
}
printf("\n");
return 0;
}
上一篇: 学python的第七天 啦啦啦啦