最大公约数&最小公倍数

最大公约数与最小公倍数

最大公因数（Greatest Common Divisor(GCD) ,Highest Common Factor(HCF)），也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数（Least Common Multiple（LCM））（两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数）。a，b的最小公倍数记为[a，b]。

最重要性质

gcd(a,b)=gcd(b, a mod b)
最大公约数与最小公倍数关系：gcd(a, b) * lcm(a, b) = ab
更详细的介绍：百度：最大公约数
百度：最小公倍数

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
//暴力法，直接枚举
void GCD1(int m,int n)
{
int i,factor=1;
for(i=2;i<=m&&i<=n;i++)
{
while(m%i==0&&n%i==0)//这里不能用if,因为可能有重复的公因子，例如12和24
{
factor=factor*i;
m/=i;
n/=i;
}
}
cout<<"GCD1:
"<<factor<<endl;
}
/**
* GCD(m,n)=GCD(m+kn,n)=GCD(m%n,n)
*/
void GCD2(int m,int n)
{
int r=m%n;
//GCD(r=m%n,n)=GCD(n,r)
while(r)
{
m=n;
n=r;
r=m%n;
}
cout<<"GCD2:
"<<n<<endl;
}
int main()
{
GCD1(12,72);
GCD2(12,73);
cout << "Hello world!" << endl;
return 0;
}

最小公倍数就略了，因为lcm(a,b)=a*b/gcd(a,b)

最后

以上就是忧伤柠檬为你收集整理的最大公约数&最小公倍数的全部内容，希望文章能够帮你解决最大公约数&最小公倍数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。