【数论】 质数知识总结（质数判断、筛选、质因子分解、互质）

质数，又称素数，若一个正整数无法被除了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] prime[1]遍历到 p r i m e [ i ] ∗ p r i m e [ i ] ≤ N prime[i]*prime[i]≤N prime[i]∗prime[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)，所以称为线性筛

实现：

对于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=P1a1​​⋅P2a2​​⋅P3a3​​⋅⋅⋅Pmam​​

这个定理看似非常简单，但是在很多地方都会应用到，要有将一个数分解为质因子幂次乘积的思想

分解质因子：

如果还想知道每个质因子的幂次再用一个数组存就行

最大公约数：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互质。

具体信息可见：欧拉函数计算及打表