质数定义
质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。
在整个自然数集合中,质数的数量不多,分布比较稀疏,对于一个足够大的整数\(N\),不超过\(N\) 的质数大约有\(N/lnN\)个,即每\(lnN\)个数中大约有1个质数。
质数的判定
试除法
概述
我们只需要扫描2~\(sqrt(N)\)之间的所有整数,依次检查它们是否能整除\(N\),需要特判0与1两个整数
该算法时间复杂度为\(O(sqrt(N))\)
模板代码
bool isPrime(int n){
if(n<2) return 0;
for(int i=2;i<=sqrt(n);i++){
if(n%i==0) return 0;
}
return 1;
}
质数的筛选
埃氏筛
由于其时间复杂度并非最小,在此不做介绍
欧拉筛(线性筛法)
概述
线性筛法通过“从大到小累积质因子”的方式标记每个合数
模板代码
int n,Prime[100010],cnt;
bool isPrime[100010];
void check(){
memset(isPrime,1,sizeof(isPrime));
isPrime[1]=0;
for(int i=2;i<=n;i++){
if(isPrime[i]) Prime[++cnt]=i;
for(int j=1;j<=cnt&&i*Prime[j]<=n;j++){
isPrime[i*Prime[j]]=0;
if(!i%Prime[j]) break;
}
}
}
例题
P1304 哥德巴赫猜想
P1075 [NOIP2012 普及组] 质因数分解
P1579 哥德巴赫猜想(升级版)
P1036 [NOIP2002 普及组] 选数
P2626 斐波那契数列(升级版)