用辗转相除法(欧几里德法)求最大公约数
时间: 2023-06-11 20:08:36 浏览: 259
辗转相除法,又称欧几里得算法,是求两个正整数的最大公约数的一种方法。
假设需要求的两个整数分别为a、b(a>b),则按照辗转相除法的步骤,可以得到如下算法:
1. 用b去除a,得到商q和余数r(r=b-aq)。
2. 如果r=0,则b即为最大公约数。
3. 如果r≠0,则用b除以r,得到商q1和余数r1(r1=b-qr)。
4. 如果r1=0,则r即为最大公约数。
5. 如果r1≠0,则继续用r去除r1,得到商q2和余数r2,重复步骤4,直到余数为0为止。
按照上述算法,可以求得a和b的最大公约数gcd(a,b)。
下面是一个使用Python实现辗转相除法的示例代码:
```python
def gcd(a, b):
while b:
a, b = b, a % b
return a
```
这个函数会返回a和b的最大公约数。
相关问题
java辗转相除法求最大公约数
在Java中,可以使用辗转相除法来求两个数的最大公约数。辗转相除法是一种求最大公约数的方法,也叫做欧几里德算法。具体的代码如下所示:
```java
import java.util.Scanner;
public class GCD {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.print("请输入两个数:");
int a = in.nextInt();
int b = in.nextInt();
while (b > 0) {
int r = a % b;
a = b;
b = r;
}
System.out.println("最大公约数是:" + a);
}
}
```
以上代码通过辗转相除法,对输入的两个数进行取余操作。具体来说,就是用较大的数除以较小的数,如果余数不为零,则将余数和较小的数构成新的一对数,继续上面的除法,直到大数被小数除尽,这时较小的数就是原来两个数的最大公约数。这个代码中使用了while循环,不断进行取余操作,直到余数为零。最后,输出的结果就是最大公约数。
辗转相除法求最大公约数Python
辗转相除法,也称为欧几里德算法,是一种用于求解两个整数的最大公约数的方法。它基于以下原理:两个整数a和b(a>b),它们的最大公约数等于b和a%b的最大公约数。
以下是使用Python实现辗转相除法求最大公约数的代码:
```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)
```