用求两个整数的最大公约数
时间: 2023-12-10 20:59:17 浏览: 31
可以使用辗转相除法(也叫欧几里得算法)求两个整数的最大公约数,步骤如下:
1. 将两个数中较大的数除以较小的数,得到商和余数。
2. 如果余数为 0,则较小的数即为最大公约数。
3. 如果余数不为 0,则将较小的数设为被除数,余数设为除数,继续进行第一步。
4. 重复上述步骤直到余数为 0。
下面是一个示例代码:
```python
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
# 测试
print(gcd(24, 36)) # 输出 12
```
以上代码中,gcd 函数接收两个整数 a 和 b,然后执行辗转相除法求它们的最大公约数。在 while 循环中,每次用 b 去除 a,然后将 a 赋值给 b,将 a 取余 b 的结果赋值给 a,直到 b 等于 0,此时 a 就是最大公约数。
相关问题
求两个整数最大公因数
根据提供的两个引用,可以得到求两个整数最大公因数的算法步骤如下:
1. 设两个整数为a和b,令i等于a和b中的较小值。
2. 若a和b能同时被i整除,则i即为最大公约数,结束。
3. 若不能,则i减1,再回去执行第2步。
代码实现如下(C++):
```
#include <iostream>
using namespace std;
int gcd(int a, int b) {
int i = min(a, b);
while (i > 0) {
if (a % i == 0 && b % i == 0) {
return i;
}
i--;
}
return 1;
}
int main() {
int a, b;
cout << "请输入两个整数:";
cin >> a >> b;
cout << a << "和" << b << "的最大公约数为:" << gcd(a, b) << endl;
return 0;
}
```
C语言函数求两个整数最大公约数
以下是一个用C语言函数求两个整数最大公约数的例子:
```c
#include <stdio.h>
int gcd(int x, int y) {
int z = x % y;
while (z) {
x = y;
y = z;
z = x % y;
}
return y;
}
int main() {
int a, b;
scanf("%d %d", &a, &b);
printf("最大公约数为:%d\n", gcd(a, b));
return 0;
}
```