目录
讲丶数学
素数定义:
合数定义:
质数个数:
算数基本定理:
算数基本定理的推论:
贰 质数的判定
叄 质数筛法
Eratosthenes 筛法(埃拉托斯特尼筛法):
线性筛法:
讲丶数学
素数定义:
素数是指在大于 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\)记录每个数的最小质因子, 按照下面的步骤来操作:
依次考虑 2~\(N\)之间的每个数 \(i\);
若 \(pf[i]=i\), 则 \(i\)是质数;
扫描不大于 \(v[i]\)的每个质数 \(p\), 令 \(pf[i*p]=p\).
这样每个合数 \(i*p\), 只会被最小质因数 \(p\)标记一次, 时间复杂度为 \(O(N)\);
讲丶数学
来源: http://www.bubuko.com/infodetail-3358256.html