如何求两个数的最大公约数
时间: 2023-09-26 11:09:11 浏览: 27
求两个数的最大公约数有多种方法,这里介绍两种常见的方法:
1. 辗转相除法(欧几里得算法):假设两个数为a和b,其中a>b,用a除以b得到余数c,然后把b作为被除数,c作为除数,再用b除以c得到余数d,如此反复,直到余数为0,此时的除数即为a和b的最大公约数。
2. 更相减损术:假设两个数为a和b,其中a>b,用a减去b得到差c,然后把b作为被减数,c作为减数,再用b减去c得到差d,如此反复,直到差为0,此时的被减数即为a和b的最大公约数。
下面是Python代码实现:
1. 辗转相除法
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
```
2. 更相减损术
```python
def gcd(a, b):
if a == b:
return a
elif a > b:
return gcd(a - b, b)
else:
return gcd(a, b - a)
```
相关问题
辗转相除求两个数最大公约数
辗转相除法,也叫欧几里得算法,是求两个数最大公约数的常用方法。
假设要求两个数a和b的最大公约数,可以按照以下步骤进行:
1. 用a除以b,得到商q和余数r,即a = bq + r。
2. 如果r等于0,则b就是最大公约数。
3. 如果r不等于0,则用b除以r,得到商q1和余数r1,即b = rq1 + r1。
4. 重复步骤2和3,直到余数为0为止。最后的除数就是最大公约数。
例如,求48和30的最大公约数:
48 ÷ 30 = 1 余18
30 ÷ 18 = 1 余12
18 ÷ 12 = 1 余6
12 ÷ 6 = 2 余0
因此,48和30的最大公约数为6。
简单的 Python 代码如下:
```
def gcd(a, b):
while b:
a, b = b, a % b
return a
print(gcd(48, 30)) # 输出6
```
c语言怎么求两个数最大公因数
求两个数的最大公因数可以使用辗转相除法,具体步骤如下:
1. 先找出这两个数中最小的那个,可以用i表示。
2. 然后用这两个数依次对i取余。同时i不断减1,直到这两个数对i取余都为0;这时的i就为最大公因数。
下面是一个C语言的代码实现:
```
#include <stdio.h>
int main() {
int m, n, min;
int i;
scanf("%d%d", &m, &n);
min = m > n ? n : m; //条件运算符
for (i = min; i >= 1; i--) //公约数范围
{
if (m % i == 0 && n % i == 0) //被两个数同时整除
{
printf("最大公约数为:%d \n", i);
break; //若可整除,一定是最大,就break
}
}
return 0;
}
```