质数基础¶
惟一分解定理¶
\(m=\prod p_i^{l_i}\)，即质因数分解，有且仅有一种情况。
质因数分解¶
每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数。如30=2×3×5 。分解质因数只针对合数。
算法实现：
-
筛质数表
-
从小到大遍历质数表，当发现i是n的因数(n%i==0)时不断把n除以i直到不包含因数 \(i(n\%i!=0)\)，同时记录i的个数cnt[i]++
-
结束条件 $ i^2>n$ （当 \(i^2>n\) 时，假设 \(i*j=n\)，那么 \(j\) 一定小于
sqrt(n)，一定会在之前就被筛掉） -
中途结束条件：\(n=1\)
-
结束后特殊判定：如果\(n≠1\)，那么此时 \(n\) 也是原数的一个因数。（请说明为何会出现这种情况）
算法实现
hole
因数个数¶
一个正整数数n的所有的约数个数的一个比较实用的上界是\(2\sqrt n\)。
一个数的质因数个数比较松的上限是\(\log_2x\)
单个素数判定（素性判定）¶
参考 Miller–Rabin 素性测试