质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。
([1,N]) 中的素数大概有 (N/InN) 个
I.素数判断
首先，根据定义，我们可以枚举((1,n)) 里的数，若存在 (i) 使得 (i|n) ,
则 (n) 是合数，否则 (n) 是质数。
但其实不用枚举到 (n) , 因为 (n) 如果是合数，则其必定有一个小于等于 (sqrt{n}) 的因子。
所以枚举到 ([sqrt{n}]) 即可。
bool ifprime(LL x)
{
int i;
for(i=2;i*i<=x;i++)
if(x%i==0)
return false;
return true;
}
常数更小的筛法
把每一个数都表示成 (6x+y,(x,yin N)) 的形式。
那么有
- (6x+0) 可以被 2,3,6 整除
- (6x+1) 待定
- (6x+2) 可以被 2 整除
- (6x+3) 可以被 3 整除
- (6x+4) 可以被 2 整除
- (6x+5) 待定
先判断 (n) 能否被 (2,3) 整除(假定$n in [4,+infty] $)
- 若能则 (n) 不是质数
- 否则枚举 (x in {x|x=6k+1,kin Z} cup {x|x=6k+5,kin Z}) ,判断 (n) 能否整除 (x)
- (n in [1,3]) 时，特判掉即可。
bool isprime(LL x)
{
if(x==2||x==3) return 1;
if(x%6!=1&&x%6!=5) return 0;
for(int i=5;i*i<=x;i+=6)
if(x%i==0||x%(i+2)==0)
return 0;
return 1;
}
上述算法的实际运行次数大约为 $ sqrt{n} div 6$
II.素数筛法
1.朴素筛法
时间复杂度(O(n^{3/2}))
很容易想到从1枚举到n，挨个判断是不是素数；
Code：
void Prime()
{
int i,j;
for(i=2;i<=n;i++) {
if(isprime(i))
pm[++tot]=i;
}
return;
}
isprime 函数可参考素数判断的内容。
2.简单筛法
令A为素数，则A*N（N>1;N为自然数）都不是素数，标记为合数。
时间复杂度(O(nlogn))
Code:
const LL N=1e7+5;
int pm[N];
bool tag[N];
int tot;
void Prime()
{
int i,j;
for(i=2;i<=n;i++) {
if(!tag[i])
pm[++tot]=i;
for(j=2*i;j<=n;j+=i)
tag[j]=true;
}
return;
}
优点：稍微改造一下可以标记出 ([1,n]) 中所有数的约数。
缺点：时间复杂度。
推论：([1,n]) 中所有数的约数数量之和约为 (nlogn) .
3.Eratosthenes筛法
(埃拉托色尼斯筛法)
埃氏筛法其实是对 2 的优化。
-
若 (x) 已经被标记为合数，则不用 (x) 去标记其他数。
- 据理：(x) 是一个合数，则 (x) 起码有两个质因子 (y),(z)。
- 且 (y,z<x) , 观察上述算法流程，可发现所有能被 (x) 筛掉的数已经被 (y,z) 即 (x) 的其他质因子筛掉一遍了。
- 值得一提的是，单用（2和优化1）时，可以标记出 ([1,n]) 中所有数的质因数。
-
二是 (i) 若为素数，则从 (i*i) 开始标记合数。
- 据理：对于 任意 (x in (i,i*i)) ,若 (i|x) ，则 (x) 必有另一个约数 (<i) .
- 证明： (x/i) 是 (x) 的一个约数，且其比 i 小。
- 所以： ((i,i*i)) 里的数已经被比i小的数标记过了，(i) 从 (i*i) 开始标记。
Code：
void prime()
{
LL i,j;
for(i=2;i<=n;i++)
{
if(tag[i]) continue; //优化1
pm[++tot]=i;
for(j=i*i;j<=n;j=j+i) //优化2
tag[j]=true;
}
}
上述算法的时间复杂度为：(O(nloglogn)).
证明在此：https://www.zhihu.com/question/35112789。
图片来自：https://zhuanlan.zhihu.com/p/48560969
4.线性筛法---Euler筛
观察Eratosthenes筛法的动图，我们发现有些数比如110，还是被筛了多次。
我们不妨规定一个顺序，让每个合数只被他的最小质因子筛掉。
一个形象的说法就是，对于每一个数，配合比他的最小的一个质因子还小的质数 (x)，筛掉合数。
((x) 筛掉的合数 的最小质因子 就是 (x))
这样每个数都只会被其最小的质因子筛掉一次。
时间复杂度(O(n))
Code:
void Prime()
{
int i,j;
for(i=2;i<=n;i++) {
if(!tag[i])
pm[++tot]=i;
for(j=1;j<=tot;j++) { //配合其他质数
if(i*pm[j]>n) break; //越界
tag[i*pm[j]]=true; // 标记合数
if(i%pm[j]==0) // 若pm[j]|i,那么 pm[j+1]*i 的最小质因子就是 pm[j] 而不是 pm[j+1] 了
break; // 违反的上述规定，于是就break掉
} // 关于 pm[j+1]*i ，不用担心,他会被 pm[j] 配合其他某个数筛掉
} // 这样就做到了不重不漏
return;
}
END
1000000以内的质数请见：https://cjlworld.blog.luogu.org/zhi-shuo-biao
(10^{10}) 以内的质数请见：
- 链接：https://pan.baidu.com/s/1E0Z6JXTy7ZskOUeexQJjGQ
- 提取码：v7u3