问题提出
设计一个函数将指定范围(比如[1,10000])中的所有素数标记出来，利用arr[10001],如果i是素数，则arr[i]==1,否则，arr[i]==0;
思路分析
一个最简单的思路，逐个枚举遍历（当然并不可行）：
//对一个单独的数字n判断是否为素数,若要判断多个，依次循环呗啊😉
int prime(int n){
for(int j=2;j*j<=n;++j){
if(n%j==0) return -1;
}
return 0;
}
素数筛算法的思路：
给出要筛数值的范围n，找出 以内的所有素数，然后先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去......。
具体过程如图所示：
素数筛算法图示
实现代码
#include<stdio.h>
int prime[10006]={0};
//素数筛算法
void init_prime(){
for(int i=2;i*i<=10000;++i){
if(prime[i]==0){
for(int j=2*i;j<=10000;j+=i)//用j枚举该素数i的所有倍数
prime[j]=1;//将j标记为合数
}
}
return;
}
int main(){
init_prime();
for(int i=2;i<=10000;++i)
if(prime[i]==0) printf("%d ",i);
printf("\n");
return 0;
}
参考埃拉托斯特尼筛法
最后
今天的分享就到这里就要结束了，希望对大家有所收获。码字不易，希望多多转发分享~
欢迎关注我的个人公众号【小超说】，后台回复 算法01 送你一份 算法与数据结构思维导图
最后，欢迎关注我，我们一起进步，成长！
img
