求两个数mn的最大公约数
时间: 2024-02-04 18:05:08 浏览: 26
请问您需要什么编程语言的代码呢?这里提供Python和Java的代码示例。
Python代码:
```python
def gcd(m, n):
if n == 0:
return m
return gcd(n, m % n)
```
Java代码:
```java
public static int gcd(int m, int n) {
if (n == 0) {
return m;
}
return gcd(n, m % n);
}
```
相关问题
分解质因数法求两个数 的最大公约数C语言的代码
以下是一份使用欧几里得辗转相减和分解质因数的C语言代码来求两个数的最大公约数:
```c
#include <stdio.h>
// 计算最大公约数
int gcd(int a, int b) {
// 辗转相减法
while (a != b) {
if (a > b) {
a = a - b;
} else {
b = b - a;
}
}
return a;
}
// 分解质因数
void factorize(int n, int factors[]) {
int index = 0;
int i = 2;
while (n > 1) {
if (n % i == 0) {
factors[index] = i;
index++;
n /= i;
} else {
i++;
}
}
}
int main() {
int num1, num2;
printf("请输入两个正整数,以空格隔开:\n");
scanf("%d %d", &num1, &num2);
// 分解质因数
int factors1[100] = {0};
int factors2[100] = {0};
factorize(num1, factors1);
factorize(num2, factors2);
// 计算公约数
int i = 0, j = 0;
int commonFactors[100] = {0};
while (factors1[i] != 0 && factors2[j] != 0) {
if (factors1[i] == factors2[j]) {
commonFactors[i] = factors1[i];
i++;
j++;
} else if (factors1[i] < factors2[j]) {
i++;
} else {
j++;
}
}
// 计算最大公约数
int result = 1;
for (int k = 0; k < 100; k++) {
if (commonFactors[k] != 0) {
result *= commonFactors[k];
}
}
printf("最大公约数是:%d\n", result);
return 0;
}
```
该代码将输入的两个数分别进行分解质因数,然后将它们的公共因子保存到一个数组中。最后,将这些公共因子相乘得到最大公约数。
获取两个数的最大公约数
您好!我可以为您提供这个问题的解答。获取两个数的最大公约数可以使用欧几里得算法或辗转相除法。
欧几里得算法:
设a,b为两个正整数,且a>b,则有 a = k*b + r,其中k为a÷b的商,r为a÷b的余数。
若r=0,则b为最大公约数。
否则,b与r的最大公约数即为a和b的最大公约数。
算法实现:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
```
辗转相除法:
设a,b为两个正整数,且a>b,则有a = k*b + r,其中k为a÷b的商,r为a÷b的余数。
若r=0,则b为最大公约数。
否则,对b和r进行相同的操作,直到余数为0。
算法实现:
```python
def gcd(a, b):
while b:
a, b = b, a % b
return a
```
希望这个解答能够帮您解决问题!
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)