一.定义
质数，又称素数，若一个正整数无法被除了1和它自身以外的其它数整除，则称其为质数，否则为合数。特殊地，1既不是合数也不是质数
二.质数的判断
试除法：
检查所有可能成为n的因子的数，若没有找到因子，则证明这个数是一个质数
一种朴素的做法就是从2遍历到N-1观察有无N的因子，若没有则说明N为质数，依据的想法是N的因子必然在1~N的范围内
改进：
其实我们只要找到一个N的因子（除了1和它本身）就可以证明N是个合数。
定理：如果N是一个合数，则必然存在一个N的因子T，满足
2
≤
T
≤
√
N
2≤T≤√N
2
≤
T
≤
√
N
证明：反证法即可
因此我们只需要从2遍历到√N即可，时间复杂度缩小为O（√N）
其它的想法：
素数筛进行预处理，用prime数组存放所有素数，然后从
p
r
i
m
e
[
1
]
prime[1]
p
r
i
m
e
[
1
]
遍历到
p
r
i
m
e
[
i
]
∗
p
r
i
m
e
[
i
]
≤
N
prime[i]*prime[i]≤N
p
r
i
m
e
[
i
]
∗
p
r
i
m
e
[
i
]
≤
N
，因为N如果是合数，则必然存在小于等于√N的素数因子
证明：前文以经证明过必然存在小于√N的因子，如果这个因子是素数自不必说，如果是合数，那么合数可以被分解为素因子的乘积。
目的：可以进一步减少时间复杂度，需要遍历的数更少了（因为素数的分布相对稀疏，10万以内的素数只有9500多个）
当然这只是我个人的想法，没有仔细的验证与思考，并且大部分时候O（√N）的复杂度就已经很优秀了
三.质数的筛选
筛选：即从1~N中筛选出所有的质数
思路
：一个数x的倍数——2x,3x,4x……必然不是素数
具体做法
：从2开始扫描所有的数x，并将x的所有倍数标记为合数。如果扫描到一个数y，发现y没被标记过，说明y一定是素数，因为2~y-1没有y的因子，符合素数定义
因为每个合数必然有质因子，所以只让素数来进行标记的工作以减少重复标记，比如27让3来标记为合数即可。
这就是埃氏筛
缺点：有些数仍会被重复标记，比如12既是3的倍数又是2的倍数
改进：
线性筛/欧拉筛：
即找到一个数的唯一产生方式：让一个数的
最小质因子
对其进行标记，比如12，虽然有2，3两个质因子，但只让2来标记12。
时间复杂度接近
O
(
N
)
O(N)
O
(
N
)
，所以称为线性筛
实现：
int Prime[100005];
bool Isprime[100005];
int cnt=1;
void Prime_excel(){
for(int i=2;i<=100000;i++) Isprime[i]=1;
for(int i=2;i<=100000;i++){
if(Isprime[i]) Prime[cnt++]=i;
for(int j=1;j<cnt&&Prime[j]*i<=100000;j++){
Isprime[Prime[j]*i]=0;
if(i%Prime[j]==0)
break;
}
}
}
对于
if(i%Prime[j]==0) break;
的解释：
线性筛的思想是只让
最小质因子
对合数进行标记，也就是：
Isprime[Prime[j]*i]=0;
这句话，这里Prime[j]即最小质因子。
如果
i%Prime[j]==0
，不妨将i表示为k*Prime[j]，如果令j++继续筛下去的话，下一个要筛的数是
Prime[j+1]*i
，显然这个数的最小质因子应该是Prime[j]而不是Prime[j+1]，违背了线性筛的思想，所以需要break
四.质因子分解
算术基本定理：
任何一个大于1的正整数都可以被分解为质因子的幂次的积
即
N
=
P
1
a
1
⋅
P
2
a
2
⋅
P
3
a
3
⋅
⋅
⋅
P
m
a
m
N=P_1^{a_1}\cdot P_2^{a_2}\cdot P_3^{a_3}\cdot\cdot\cdot P_m^{a_m}
N
=
P
1
a
1
⋅
P
2
a
2
⋅
P
3
a
3
⋅
⋅
⋅
P
m
a
m
这个定理看似非常简单，但是在很多地方都会应用到，要有将一个数分解为质因子幂次乘积的思想
分解质因子：
int factor[100];
int cnt=0;
void divide(int N){
cnt=0;
for(int i=2;i*i<=N;i++){
if(N%i==0){
factor[cnt++]=i;
while(N%i==0)
N/=i;
}
}
if(N>1) factor[cnt++]=N; //质数在根号N内没有因子，故可能没除完
}
如果还想知道每个质因子的幂次再用一个数组存就行
五.互质
最大公约数：great common divisor，简称gcd
互质定义：若gcd(a,b)=1，则称a与b互质
关于欧几里得算法求gcd的证明：
欧几里得算法证明
欧拉函数：
在数论中，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目（因此φ(1)=1）。此函数以其首名研究者欧拉命名(Euler’s totient function)，它又称为Euler’s totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。
具体信息可见：
欧拉函数计算及打表