求最大公约数和最小公倍数

简介: 求最大公约数和最小公倍数

最大公约数

碾转相除法:①gcd(la, b)=gcd(b, a%b) ②0的最大公约数就是另一个数

最小公倍数

两个数的乘积等于这两个数的最大公约数与最小公倍数的积。最小公倍数就是a * b / gcd(a, b)。

int gcd(long a, long b)
{
  return b == 0 ? a : gcd(b, a % b);//gcd(a,b) = gcd(b,a % b)   0的最大公约数就是另一个数
}
int lcm(int a, int b) {//两个数的乘积等于这两个数的最大公约数与最小公倍数的积。即(a,b)×[a,b]=a×b
  if (a == 0 || b == 0) {
    return 0;
  }
  return a * b / gcd(a, b);
}
int main() {
  long a = 12;
  long b = 36;
  cout << gcd(a, b)<<endl;
  cout << lcm(a, b) << endl;
}
相关文章
|
6月前
|
JavaScript 前端开发 Java
最大公约数
【6月更文挑战第23天】
74 4
|
6月前
|
移动开发 算法
最大公约数和最小公倍数
【6月更文挑战第8天】最大公约数和最小公倍数。
66 9
|
6月前
每日一数——最大公约数与最小公倍数
每日一数——最大公约数与最小公倍数
求最小公倍数
求最小公倍数
128 0
|
7月前
|
算法
详解最大公约数和最小公倍数
详解最大公约数和最小公倍数
求最大公约数
求最大公约数
78 0
|
人工智能 BI
求最大公约数和最小公倍数
求最大公约数和最小公倍数
91 0
求最小公倍数!
求最小公倍数!
101 0
求最大公约数最小公倍数
求最大公约数最小公倍数
119 0