用辗转相除法求两个整数公约数
时间: 2023-07-16 07:14:08 浏览: 55
辗转相除法,也叫欧几里得算法,是求最大公约数的一种常用方法。
假设要求两个正整数a和b的最大公约数,用辗转相除法的步骤如下:
1. 用a除以b,得到商q和余数r;
2. 如果r等于0,则b就是最大公约数;
3. 如果r不等于0,则用b除以r,得到商q'和余数r';
4. 如此反复,直到余数为0,则最后一个非零余数的除数就是a和b的最大公约数。
以下是辗转相除法的Python代码实现:
```python
def gcd(a, b):
while b != 0:
r = a % b
a = b
b = r
return a
```
其中,a代表第一个整数,b代表第二个整数。
相关问题
编写c语言程序,用辗转相除法求两个整数公约数
以下是使用辗转相除法求两个整数公约数的C语言程序:
```c
#include <stdio.h>
int main() {
int num1, num2, remainder;
printf("请输入两个整数:\n");
scanf("%d %d", &num1, &num2);
while (num2 != 0) {
remainder = num1 % num2;
num1 = num2;
num2 = remainder;
}
printf("它们的公约数为:%d\n", num1);
return 0;
}
```
程序先要求用户输入两个整数,然后使用while循环来不断进行辗转相除的操作,直到其中一个数变为0为止。最后输出剩下的那个数,即为它们的最大公约数。
C语言用辗转相除法求两个整数的最大公约数
辗转相除法,也称欧几里得算法,是求解两个数的最大公约数的一种常用方法。其基本思想是:用较大的数除以较小的数,再用除数除以出现的余数(第一次除的余数是较小的数,第二次除的余数是第一次的余数除以第二次的除数所得的余数,以此类推),直到余数为0为止。此时,除数即为这两个数的最大公约数。
下面是使用 C 语言实现辗转相除法求两个整数的最大公约数的示例代码:
```c
#include <stdio.h>
// 求两个整数的最大公约数
int gcd(int a, int b)
{
int temp;
while (b != 0)
{
temp = a % b;
a = b;
b = temp;
}
return a;
}
int main()
{
int a, b;
printf("请输入两个整数:");
scanf("%d %d", &a, &b);
printf("%d 和 %d 的最大公约数为 %d", a, b, gcd(a, b));
return 0;
}
```
输入两个整数,程序即可输出它们的最大公约数。