概述
线性筛的原理：
线性筛其实就是在埃氏筛的基础上多了一个判断，满足就退出，可以省时间。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=999999;
int cnt,n;
int a[N];
bool b[N];//0 质数 1 非质数
void get_prime(int n){
b[0]=1,b[1]=1;//先将0和1解决好
for(int i=2;i<=n;i++){
if(!b[i])a[cnt++]=i;
for(int j=0;a[j]*i<=n;j++){
b[a[j]*i]=1;
if(i%a[j]==0)break;
}
}
return;
}
int main(){
cin>>n;
get_prime(n);
cout<<cnt<<"n";
for(int i=0;i<cnt;i++)
cout<<a[i]<<' ';
return 0;
}最后
以上就是清爽路人为你收集整理的求质数的方法——线性筛法的全部内容，希望文章能够帮你解决求质数的方法——线性筛法所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复