求解质数的解题方法有以下几种,分别是
1、朴素法,用于小范围数据的时候将每一个倍数都剔除掉
解法一:朴素法
时间复杂度为O(NlogN)
#include<bits/stdc++.h>
using namespace std;
//使用一个数组存储所有的质数,使用一个数字记录下标
const int N=1E6+10;
int primes[N],curr;
bool st[N];
int main()
{
int n;
cin>>n;
for(int i=2;i<=n;i++)
{
//判断数字标志是否为合数
if(!st[i])
{
primes[curr]=i;
curr++;
}
//朴素的做法是把每一个倍数都删除
for(int j=i+i;j<=n;j+=i)
{
st[j]=true;
}
}
cout<<curr;
return 0;
}
解法二:诶氏筛法 O(nloglogn)
#include<bits/stdc++.h>
using namespace std;
//使用一个数组存储所有的质数,使用一个数字记录下标
const int N=1E6+10;
int primes[N],curr;
bool st[N];
int main()
{
int n;
cin>>n;
for(int i=2;i<=n;i++)
{
//判断数字标志是否为合数
if(!st[i])
{
primes[curr]=i;
curr++;
for(int j=i+i;j<=n;j+=i)
{
st[j]=true;
}
}
}
cout<<curr;
return 0;
}
解法三:线性筛
为了防止重复计算,每次循环遇到自己的最小质因数就结束循环。