用C语言实现,编写函数得到最小公倍数,至少用两种方法
时间: 2024-03-12 10:42:56 浏览: 25
除了上面提到的利用最大公约数求最小公倍数的方法外,还可以使用以下两种方法来实现求最小公倍数的函数:
方法一:暴力枚举法
此方法的思路是从两个数的较大值开始,一直往上枚举,直到找到一个数,使得这两个数同时能被它整除。具体实现代码如下:
```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 lcm = max;
while (lcm % min != 0) {
lcm += max;
}
return lcm;
}
```
需要注意的是,以上两种方法都可以求得最小公倍数,但是它们的时间复杂度都比较高,不太适用于大数据的计算。因此,在实际的应用中,我们更多地会使用利用最大公约数来求最小公倍数的方法。
相关问题
用C语言实现,编写函数得到最小公倍数,至少用三种方法
方法一:使用最大公约数
最小公倍数等于两数之积除以它们的最大公约数。
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的较大值。
用C语言实现,编写函数得到最小公倍数
可以使用以下的方法来实现求最小公倍数的函数:
```c
int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
```
其中,`gcd()`函数用于求两个数的最大公约数,`lcm()`函数则是利用最大公约数来求得最小公倍数。
需要注意的是,在使用这两个函数时,输入的参数应该保证都为正整数。