c++实现最大公因数和最小公倍数

 最大公因数和最小公倍数的介绍

读这篇文章，请你先对最大公因数以及最小公倍数进行了解：

最大公因数（英文名：gcd）

• 定义：最大公因数，也称最大公约数，指两个或多个整数共有约数（因数）中最大的一个。
• 求法
  • 列举法：分别列出两个数的所有约数，然后找出它们共有的约数中最大的那个。
  • 分解质因数法：
  • 辗转相除法：用较大数除以较小数得到商和余数，再用除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公因数。

• 最小公倍数（英文名：lcm）

  • 几个数共有的倍数叫做这几个数的公倍数，其中除 0 以外最小的一个公倍数，叫做这几个数的最小公倍数。例如，4 的倍数有 4、8、12、16、20、24……，6 的倍数有 6、12、18、24、30……，4 和 6 的公倍数有 12、24……，其中最小的是 12，所以 4 和 6 的最小公倍数是 12，可记作[4,6]:12。
  • 求法
    • 列举法：分别列出两个数的倍数，然后找出它们共有的倍数中最小的那个。如求 3 和 5 的最小公倍数，3 的倍数有 3、6、9、12、15、18……，5 的倍数有 5、10、15、20……，它们的最小公倍数是 15。
  • 分解质因数法：把它们公有的质因数与每个数独有的质因数连乘起来，所得的积就是它们的最小公倍数。例如，12=2×2×3，15=3×5，所以
  • 公式法：对于两个数a和b，[a,b]=a*b/(a,b)。例如：

代码：

#include <bits/stdc++.h>
using namespace std;
long long x=0,y=0;
long long pri[100000],cnt=0;
long long gcd(long long a,long long b) {return !b?a:gcd(b,a%b);
}
void gprime(long long num) {cout<<num<<"=";long long divisor=2;bool first=true;while(num>1) {if(num%divisor==0) {if(!first) {cout<<"*";}cout<<divisor;num/=divisor;first=false;} else {divisor++;}}cout<<endl;
}
vector<long long>commonFactors(long long a,long long b) {vector<long long>factors;for(long long i=1; i<=min(a,b); i++) {if(a%i==0&&b%i==0) {factors.push_back(i);}}return factors;
}
long long poww(long long x) {long long f1=x,cnt=0;while(f1) {f1/=10;cnt++;}return cnt;
}
bool Is_Prime(long long x) {for(long long i=2; i<x; i++) {if(x%i==0) {return 0;}}return 1;
}
void Print(long long a,long long b) {cout<<"分解质因数过程:"<<endl;gprime(a);gprime(b);vector<long long>factors=commonFactors(a,b);cout<<a<<"和"<<b<<"的公因数有:";for(long long factor:factors) {cout<<factor<<" ";}cout<<"\n";if(gcd(a,b)==1) {cout<<"互质,没有过程。\n";} else {cout<<"输出短除法过程\n";long long k=poww(a)+poww(b)+5,back;long long fa=a,fb=b;while(gcd(fa,fb)!=1) {for(long long i=2;; i++) {if(Is_Prime(i)&&fa%i==0&&fb%i==0) {cnt++;pri[cnt]=i;cout<<i<<" | "<<fa<<" "<<fb<<"\n";for(long long j=1; j<=poww(i)+1; j++) {cout<<" ";}for(long long j=1; j<=k; j++) {cout<<"-";}fa/=i;fb/=i;cout<<"\n";if(gcd(fa,fb)==1) {back=i;x=fa;y=fb;}break;}}}for(long long i=1; i<=poww(back)+3; i++) {cout<<" ";}cout<<fa<<" "<<fb<<"\n";}if(gcd(a,b)==1) {cout<<"("<<a<<","<<b<<"):"<<gcd(a,b)<<"\n";cout<<"["<<a<<","<<b<<"]:";if(gcd(a,b)==1) {cout<<a<<"*"<<b<<"\n";for(long long i=1; i<=poww(a)+poww(b)+3; i++) {cout<<" ";}cout<<"=";}cout<<a*b/gcd(a,b);return ;}cout<<"("<<a<<","<<b<<"):";long long anss=1;for(long long i=1; i<=cnt; i++) {anss*=pri[i];cout<<pri[i];if(i!=cnt) {cout<<"*";}}cout<<"\n";for(long long i=1; i<=poww(a)+poww(b)+3; i++) {cout<<" ";}cout<<"="<<anss;cout<<"\n["<<a<<","<<b<<"]:";for(long long i=1; i<=cnt; i++) {cout<<pri[i]<<"*";}cout<<x<<"*"<<y<<"\n";for(long long i=1; i<=poww(a)+poww(b)+3; i++) {cout<<" ";}cout<<"="<<anss<<"*"<<x*y<<"\n";for(long long i=1; i<=poww(a)+poww(b)+3; i++) {cout<<" ";}cout<<"="<<gcd(a,b)<<"\n";cout<<"("<<a<<","<<b<<"):"<<gcd(a,b)<<"\n";cout<<"["<<a<<","<<b<<"]:";if(gcd(a,b)==1) {cout<<a<<"*"<<b<<"\n";for(long long i=1; i<=poww(a)+poww(b)+3; i++) {cout<<" ";}cout<<"=";}cout<<a*b/gcd(a,b);
}
int main() {cout<<"输入两个整数:\n";cout<<"本程序用于计算两个数的gcd（最大公因数、最大公约数）以及lcm，其中，(a,b)表示两个数的gcd，[a,b]表示两个数的lcm\n";long long a,b;cin>>a>>b;system("cls");if(gcd(a,b)==1) {cout<<"检测到互质，将自动省略过程\n";Print(a,b);return 0;}if(gcd(a,b)==min(a,b)){cout<<"检测到有倍数关系，这里推荐使用不要过程，请慎重选择\n";}cout<<"输入模式:\n";cout<<"0.只要答案\n";cout<<"其他任何数.要过程\n";long long sr;if(!sr&&gcd(a,b)==min(a,b)){cout<<"("<<a<<","<<b<<"):"<<min(a,b)<<"\n";cout<<"["<<a<<","<<b<<"]:"<<max(a,b)<<"\n";return 0;}cin>>sr;system("cls");if(!sr) {cout<<"("<<a<<","<<b<<"):"<<gcd(a,b)<<"\n";cout<<"["<<a<<","<<b<<"]:";if(gcd(a,b)==1) {cout<<a<<"*"<<b<<"\n";for(long long i=1; i<=poww(a)+poww(b)+3; i++) {cout<<" ";}cout<<"=";}cout<<a*b/gcd(a,b);return 0;}Print(a,b);return 0;
}