利用辗转相除法——求最大公约数
时间: 2023-08-24 18:09:47 浏览: 61
辗转相除法,也称欧几里德算法,可以用来求解两个整数的最大公约数(Greatest Common Divisor,简称GCD)。其基本思想是:用较大的数除以较小的数,再用余数(第一次除法的余数是较小数,以后每次的余数是上次的除数除以这次的余数)去除较小的数,直到余数为0为止,此时除数即为最大公约数。
以下是一个使用 Python 实现辗转相除法求解最大公约数的例子:
```python
def gcd(a, b):
while b:
a, b = b, a % b
return a
```
其中,a 和 b 是需要求解最大公约数的两个整数。函数首先判断 b 是否为 0,如果是则返回 a;否则进行辗转相除法的计算,将 b 与 a%b 的值赋给 a 和 b,直到 b 变为 0,此时 a 即为最大公约数。
相关问题
用Java利用辗转相除法——求最大公约数
辗转相除法又称为欧几里得算法,可以用于求两个数的最大公约数。
Java代码如下:
```java
public class GCD {
public static int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
public static void main(String[] args) {
int a = 24, b = 60;
int result = gcd(a, b);
System.out.println("最大公约数:" + result);
}
}
```
运行结果:
```
最大公约数:12
```
其中,`gcd`方法实现了辗转相除法,如果`b`为0,返回`a`,否则递归调用`gcd`方法,参数为`b`和`a%b`。在`main`方法中,我们可以测试使用此方法求解最大公约数。
利用辗转相除法求最大公约数pta
利用辗转相除法求最大公约数的步骤如下:
1. 如果a<b,则交换a和b。
2. 用a除以b,得到余数r,如果r=0,则b就是最大公约数。
3. 如果r不等于0,则用b除以r,得到余数r1。
4. 如此反复,直到rn等于0,此时的b就是最大公约数。
以下是使用欧几里得算法(辗转相除法)求两个数的最大公约数的Python代码:
```python
def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
r = a % b
a, b = b, r
return a
```