求两个数的最大公因数
时间: 2024-06-13 14:08:56 浏览: 8
以下是两种求两个数最大公因数的方法:
1.辗转相除法
辗转相除法是求两个数最大公因数的一种简便方法,其基本思想是用较大数除以较小数,再用除数除以出现的余数(第一次除法的除数是较小数,第二次除法的除数是第一次的余数),如此反复,直到余数为零为止,此时除数就是这两个数的最大公因数。
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
a = 24
b = 36
print("最大公因数为:", gcd(a, b)) # 输出:12
```
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 = 24
b = 36
print("最大公因数为:", gcd(a, b)) # 输出:12
```
相关问题
辗转相除求两个数最大公约数
辗转相除法,也叫欧几里得算法,是求两个数最大公约数的常用方法。
假设要求两个数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;
}
```
相关推荐
![](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)