讲丶数学

壹 回顾小学数学

素数定义：

素数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

约数定义：如果存在一个整数\(k\)，使得\(a=k*d\),则称\(d\)整除\(a\)，记做\(d|a\),称\(a\)是\(d\)的倍数，如果\(d>0\),称\(d\)是\(a\)的约数。特别的任何数都整除\(0\)。

合数定义：

合数是指自然数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。

质数个数：

在自然数中，质数的个数并不多，对于一个足够大的整数\(N\),不超过\(N\)的质数大约有\(N/lnN\)个。（证明很复杂，自己上网找，理解不了就记下来）

算数基本定理：

任何一个大于1的正整数都能唯一分解为有限个质数的乘积。

\(N=p_1^{c_1}p_2^{c_2}p_3^{c_3}p_4^{c_4}……p_m^{c_m}\)

其中\(c_i\)都是正整数，\(p_i\)都是质数，且\(p_1<p_2<p_3……<p_m\).

算数基本定理的推论：

由上面的定理可知\(N\)的正约数集合可写作：

{\(p_1^{b_1}p_2^{b_2}……p_2^{b_2}\)},且\(0<=b_i<=c_i\)

\(N\)的正约数个数为\((c_1+1)(c_2+1)*……*(c_m+1)=\prod_{i=1}^m(c_i+1)\)

正约数和为\(\prod_{i=1}^m(\sum_{j=0}^{c_i}(p_i)^j)\)

贰 质数的判定

暴力试除：

若一个正整数\(N\)为合数，则存在一个能整除\(N\)的数\(T\)，且\(2<=T<=\sqrt{N}\).

所以我们暴力扫描\(2\)~\(\sqrt{N}\)的整数，若都不能整除\(N\),\(N\)就是质数。同时要特判0和1两个数，它们既不是质数，也不是合数。

叄 质数筛法

Eratosthenes 筛法（埃拉托斯特尼筛法）：

如果\(x\)为合数，那么\(x\)的倍数一定是合数。

我们可以根据上面的命题，由小到大扫描每个数\(x\),把\(2x,3x,4x……\lfloor N/x \rfloor*x\)打上标记，记为合数。当扫描到某个数后，如果没被标记，它就是合数。

这个算法的时间复杂度是\(O(\sum_{质数p<=N}N/p)=O(NloglogN)\),很接近线性，一般竞赛里都用这个方法。

线性筛法：

我们想一下，按照埃筛的方法标记的时候，会出现重复标记的情况。

比如12，它在标记2的倍数时被标记了一次，在标记3的倍数时被标记了一次。

线性筛是通过从小到大储存质因子来标记合数。

设数组\(pf\)记录每个数的最小质因子，按照下面的步骤来操作：

1. 依次考虑2~\(N\)之间的每个数\(i\);
2. 若\(pf[i]=i\),则\(i\)是质数;
3. 扫描不大于\(v[i]\)的每个质数\(p\),令\(pf[i*p]=p\).

这样每个合数\(i*p\),只会被最小质因数\(p\)标记一次，时间复杂度为\(O(N)\);