求两个数的最大公约数。
时间: 2024-02-04 20:08:16 浏览: 16
以下是两种求两个数最大公约数的方法:
1. 辗转相除法:
```python
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
num1 = 24
num2 = 36
result = gcd(num1, num2)
print("最大公约数为:", result) # 输出:12
```
2. 更相减损法:
```python
def gcd(a, b):
while a != b:
if a > b:
a = a - b
else:
b = b - a
return a
num1 = 24
num2 = 36
result = gcd(num1, num2)
print("最大公约数为:", result) # 输出: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#求两个数最大公约数
可以使用辗转相除法求两个数的最大公约数,具体实现代码如下:
```
public static int GCD(int a, int b)
{
while (b != 0)
{
int temp = a % b;
a = b;
b = temp;
}
return a;
}
```
在这个方法中,我们使用 while 循环不断对两个数进行取模运算,直到其中一个数为 0,此时另一个数就是最大公约数。