当前位置 博文首页 > 追梦赤子心：素因子分解&&素因子分解求最大公约数&&
素因子分解 就是把一个数化成 n=p1^a1*p2^a2*.....*pn^an的形式 其中p1,p2...pn都为素数；
#include <iostream>//整数素因子分解
#include <cstdio>
#include <cmath>
using namespace std;
int main()
{
int n;
while(cin>>n){
int x,count1=0;
int tn=n;
int count2=0;
for(int i=2;i<=n;i++){
if(tn%i==0){
count1=0;
++count2;
while(tn%i==0){
count1++;
tn/=i;
}
cout<<"素因子 "<<i<<" 幂指数"<<count1<<endl;
}
}
cout<<"素因子个数 "<<count2<<endl;
}
return 0;
}a=(p1^a1)*(p2^a2)*(p3^a3)…(pm^am),b=(p1^b1)*(p2^b2)*(p3^b3)…(pm^bm)
其中最小公倍数=max(ai,bi); ?最大公约数=min(ai,bi);
下面是求最大公约数的方法：
//素因子分解求最小公倍数
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
int main()
{
ll n,m;
while(cin>>n>>m){
int tn=n,tm=m;
int count1,count2;
ll lcm=1;
ll mult1=1,mult2=1;
for(int i=2;i<=max(n,m);i++){
if(tn%i==0||tm%i==0){
count1=count2;
mult1=mult2=1;
while(tn%i==0){
count1++;
tn/=i;
mult1*=i;
}
while(tm%i==0){
count2++;
tm/=i;
mult2*=i;
}
lcm=lcm*max(mult1,mult2);
}
}
printf("%lld\n",lcm);
}
return 0;
}
