辗转相除法for循环
时间: 2023-10-26 10:07:09 浏览: 74
辗转相除法,也称欧几里得算法,是求两个正整数的最大公约数的一种方法。其基本思想是用较小的数除较大的数,再用出现的余数去除除数,如此反复,直到余数为零时,最后的除数即为这两个数的最大公约数。
以下是辗转相除法的for循环实现:
```
int gcd(int a, int b) {
int temp;
while (b != 0) {
temp = a % b;
a = b;
b = temp;
}
return a;
}
```
其中,a和b为要求最大公约数的两个正整数,temp为中间变量,用于存储余数。while循环中,每次将b赋值为a%b,即将较大的数除以较小的数得到的余数赋值给b,然后将a赋值为原来的b,将b赋值为余数temp。当余数为0时,循环结束,此时a即为最大公约数。
相关问题
用for循环写辗转相除法
好的,请输入以下代码:
```
def gcd(a, b):
while(b):
a, b = b, a%b
return a
def extGcd(a, b):
x, y, u, v = 0, 1, 1, 0
while(a):
q, r = divmod(b, a)
m, n = x-u*q, y-v*q
b, a, x, y, u, v = a, r, u, v, m, n
gcd = b
return gcd, x, y
def inv(a, p):
gcd, x, y = extGcd(a, p)
assert(gcd == 1)
return x%p
a, b = map(int, input().split())
print(gcd(a, b))
```
输入两个整数,程序将输出它们的最大公约数。
c语言辗转相除法求最大公约数for循环
以下是使用C语言编写的辗转相除法求最大公约数的for循环实现:
```c
#include <stdio.h>
int main() {
int a, b, t, gcd;
scanf("%d %d", &a, &b);
for (int i = 1; i <= a && i <= b; i++) {
if (a % i == 0 && b % i == 0) {
gcd = i;
}
}
printf("%d", gcd);
return 0;
}
```
该程序首先从用户输入中读取两个整数a和b,然后使用for循环从1到a和b中较小的那个数进行遍历,如果a和b都能被当前的数整除,则将当前的数作为最大公约数gcd。最后输出gcd即可。