算术基本定理:任何一个大于1的自然数都能唯一分解为有限个质数的乘积。
[N=p^{c_1}_1 p^{c_2}_2 cdots p^{c_m}_m \
p_1 <p_2<cdots<p_m(p_i为质数) \ c_i为非负整数数
]
证明
https://baike.baidu.com/item/算术基本定理/10920095?fr=aladdin
见百度百科。。自己也看得不是很懂
质因数分解
1.试除法
我们可以扫苗2~$lfloor sqrt n
floor $的每个数d,若d能整除n,则在n中不断除去d,直至除去所有的因子d,同时记录除去d的个数。
因为每个合数的非质因子在骚猫到这个数之前就已经从n中除去了,所以上述能整除n的一定是质数。
int c[10000], p[10000];
int cnt;
inline void divide(int n) {
cnt = 0;
int t = sqrt(n);
rep(i, 2, t) {
if(n % i == 0) {//i是质数
p[++cnt] = i, c[cnt] = 0;
while(n % i == 0) n /= i, c[cnt]++;
}
}
if(n > 1) p[++cnt]=n,c[cnt]=1;//未分解完,那么剩下的也是个质数
rep(i,1,cnt) printf("%d^%d
",p[i],c[i]);
}
时间复杂度(O(sqrt n ))
2.Pollard Rho