c語言求最小公倍數(shù)的方法有哪些

小億
364
2023-08-09 05:46:42
欄目: 編程語言

在C語言中，求最小公倍數(shù)的方法有以下幾種：

  1. 暴力法：從1開始逐個(gè)嘗試兩個(gè)數(shù)的倍數(shù)，直到找到它們的公倍數(shù)。
int lcm(int a, int b)
{
int max = (a > b) ? a : b;
int lcm = max;
while (1)
{
if (lcm % a == 0 && lcm % b == 0)
break;
lcm += max;
}
return lcm;
}
  1. 輾轉(zhuǎn)相除法：利用兩個(gè)數(shù)的最大公約數(shù)來求最小公倍數(shù)。最小公倍數(shù)等于兩數(shù)的乘積除以最大公約數(shù)。
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
int lcm(int a, int b)
{
return (a * b) / gcd(a, b);
}
  1. 窮舉法：通過遍歷所有可能的公倍數(shù)，比較大小，找出最小的公倍數(shù)。
int lcm(int a, int b)
{
int max = (a > b) ? a : b;
int lcm = max;
while (1)
{
if (lcm % a == 0 && lcm % b == 0)
break;
lcm += max;
}
return lcm;
}
  1. 使用最小公約數(shù)的性質(zhì)：最小公倍數(shù)等于兩數(shù)乘積除以最大公約數(shù)。
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
int lcm(int a, int b)
{
return (a * b) / gcd(a, b);
}

這些方法都可以用來求解最小公倍數(shù)問題，具體使用哪種方法可以根據(jù)具體情況選擇。

0 踩