转自：https://blog.csdn.net/zw1996/article/details/50966032
算数基本定理
1.概念；任意一个大于0的正整数都能被表示成若干个素数的乘积且表示方法是唯一的；整理可以将相同素数的合并；可以得到
公式————n = P1^a1 * P2^a2 * …………* (P1 < P2 < ……Pn);
2.将唯一分解定理代码化；
第一步；素数打表；
以前我们素数打表都是枚举暴力进行筛选；但这种算法效果不太好，因此我们用一种更好的素数打表；
先看代码；
vis[100000] = {0},prime[100000]={0}；
for(i = 2; i <=n; i++){
if(vis[i] == 0){
prime[len] = i;
len++;
for(j = i*i; j <= n; j+= i){
vis[j] = 1;
}
}
}
是不是很很蒙的感觉；刚开始我也是这样的。让我来解释一下吧；
2；是素数，则2*2, 2*4，2*8，………直到2*2……这些都不是素数，
3；是素数，则3*3, 3*6，3*9，…………直到3*……这些都不是素数，
5；是素数，则5*5, 5*10，5*15，………直到5*……这些都不是素数，
这个规律就是上面那种筛选法的思路；
1先将数组vis【】都初始化为0；也就是最初将所有数假定义为素数
2进行上面所说的筛选；将已经确定不是素数的数的数组定义为1；
3则可以确定了 0 为素数 ； 1 为 合数；
4 prime[len] = i;这个代码的作用就是标记素数位置的；
现在是不是懂了很多；
再考虑的就是怎么往定义上去靠；
再就是求幂；
还是先看代码吧；
voidgetprimefactor(long long nn)//计算幂次方；
{
int cas=0;
for(inti=0;i<len&&prime[i]*prime[i]<=nn;i++)
{
while(nn%prime[i]==0)//可以整除；
{
factor[cas]++;
nn/=prime[i];
}
if(factor[cas] != 0)//就是进入了while里面的；
cas++;
}
if(nn>1)
factor[cas]=1; //就是因为上面for条件的原因；prime[i]*prime[i]<=nn当不满足这个条件的时候就应该还有一个素数的一次方
}
就是利用取余和整除循环来求解；
就这样；唯一分解定理也就被我们分解了；只需做题来消化了；
关于唯一分解定理的一些拓展；
1；整数a能被11整除的充要条件；
—————a的奇数为数字之和与偶数位数字之和的差能被11整除
2；n = P1^a1 * P2^a2 * …………* (P1 < P2 < ……Pn)叫做标准分解式；
Gcd = 素数里面取较小的那个累乘；
Lcm =素数里面取较小的那个累乘；
例如列子1008；1260；882；
1008 =2^4 * 3^2 * 7
1260 =2^4 * 3^2 *5 * 7
882 = 2 *3^2 * 7^2
Gcd = 2 *3^2 * 7^1 *5^0 ;
Lcm = 2^4* 3^2 * 5^1 * 7^2;