用C语言实现,编写函数得到最小公倍数,至少用三种方法
时间: 2024-03-12 13:43:38 浏览: 26
方法一:使用最大公约数
最小公倍数等于两数之积除以它们的最大公约数。
C语言实现代码如下:
```
int gcd(int a, int b) {
while (b) {
int r = a % b;
a = b;
b = r;
}
return a;
}
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
```
方法二:枚举法
先找到两个数中的较大值,然后从这个数开始向上枚举,直到找到一个数可以同时被这两个数整除为止。这个数就是它们的最小公倍数。
C语言实现代码如下:
```
int lcm(int a, int b) {
int max = a > b ? a : b;
while (1) {
if (max % a == 0 && max % b == 0) {
return max;
}
max++;
}
}
```
方法三:质因数分解法
将两个数分别进行质因数分解,然后分别统计每个质因数的最大次数,最后将这些质因数的积相乘即可得到它们的最小公倍数。
C语言实现代码如下:
```
int lcm(int a, int b) {
int max = a > b ? a : b;
int min = a < b ? a : b;
int prime[max + 1];
memset(prime, 0, sizeof(prime));
for (int i = 2; i <= max; i++) {
if (!prime[i]) {
for (int j = i * 2; j <= max; j += i) {
prime[j] = 1;
}
}
}
int factors[max + 1];
memset(factors, 0, sizeof(factors));
for (int i = 2; i <= max; i++) {
if (!prime[i]) {
int count1 = 0, count2 = 0;
int temp = max;
while (temp % i == 0) {
count1++;
temp /= i;
}
temp = min;
while (temp % i == 0) {
count2++;
temp /= i;
}
factors[i] = count1 > count2 ? count1 : count2;
}
}
int result = 1;
for (int i = 2; i <= max; i++) {
if (!prime[i]) {
result *= pow(i, factors[i]);
}
}
return result;
}
```
以上三种方法都是比较常用的求最小公倍数的方法,它们的时间复杂度不同,但都不会超过O(n^2),其中n是a和b的较大值。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)