质数判断
我们来看这么一道问题：
给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内）N<=10000000，M<=100000
首先很容易联想到使用枚举法来确定题目的整体框架
for( i: 1~m)
{
cin>>x;
if(x是质数)
{
yes;
}else
{
no;
}
}
关键在于质数判断部分。
质数的判断问题我们可以从定义出发。质数，又称素数，是除了1和它自身以外没有其他的因子。
bool isPrime(int x)
{
if(x==1) return false;
for(int i=2;i<x;i++)
{
if(x%i==0) return false;
}
return true;
}
稍微计算下整体的时间复杂度，可以发现用时会比较多，那么我们可以思考下优化的地方。整体框架确定后，能优化的地方可从质数判断入手。思考，一个数去除以比它的一半还要大的数，一定是除不尽的，因此，除到x/2就够了。
再改进一下，一个数若可以进行因数分解，那么分解得到的两个数一个范围小于sqrt(x),另一个一定大于sqrt(x)。故，上述代码我们也只需要遍历到sqrt(x)就可以了。若在2~sqrt(x)找不到约数，那么一定不存在。
bool isPrime(int x)
{
if(x==1) return false;
for(int i=2;i*i<=x;i++)
{
if(x%i==0) return false;
}
return true;
}
再进一步进行优化，偶数一定不是质数
bool isPrime(int x)
{
if(x<2) return false;
if(n%2==0) return false;
for(int i=3;i*i<=x;i+=2)
{
if(x%i==0) return false;
}
return true;
}
但当m,n很大的时侯这种方式的数量级依旧相当大。在一般的机子它不是一秒钟跑不出结果，它是好几分钟都跑不出结果。有没有更有效率的方法呢？
我们可以考虑使用筛法来进行处理。
埃氏筛
根据数学原理：一个合数总是可以分解成若干个质数的乘积，换个角度去理解，也就是说合数是某个质数的倍数。此时如果把质数的倍数都去掉，那么剩下的就是质数了。
这样的筛选方式叫做埃氏筛，也叫埃拉托色尼选筛法，是数学家埃拉托色尼提出的。
代码思路：
- 从质数2开始进行枚举
- 如果数字是质数，将范围内所有该数的倍数标记成非质数
- 继续向后枚举，直到遍历完范围内所有的数位置
代码实现：
#include <iostream>
#include <cstring>
using namespace std;
bool isPrime[10000005]={0};//标记数组 用来表示数字是否是质数 true-是质数 false-不是质数
void aiPrime(int n)
{// 埃氏筛处理n内的质数
memset(isPrime,true,sizeof(isPrime));//所有数字，默认标记为质数
isPrime[1]=false;//修改1的状态，1不是质数
for(int i=2;i<=n;i++)//从2开始，枚举范围n内的每个数字
{
if(isPrime[i])//如果i是质数
{//将n范围内所有i的倍数，标记为非质数
for(int j=2;j*i<=n;j++)
{//打底从两倍开始,j*i就是i的倍数
isPrime[i*j]=false;// 标记倍数为非质数
}
}
}
}
int main(int argc, char** argv) {
int n,m,x;
cin>>n>>m;
aiPrime(n);
for(int i=1;i<=m;i++)
{
cin>>x;
if(isPrime[x])
{
cout<<"yes\n";
}else
{
cout<<"no\n";
}
}
return 0;
}
网友评论