用循环结构求最大公约数和最小公倍数。
时间: 2023-03-24 18:00:58 浏览: 713
为了求出最大公约数和最小公倍数,我们可以使用欧几里得算法。这个算法基于一个定理,即两个正整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。换句话说,设a、b为两个正整数,a>b,令r为a÷b的余数,那么有gcd(a,b) = gcd(b,r)。
通过不断地对两个数进行取模运算,我们可以得到它们的最大公约数。具体步骤如下:
1. 用较大数除以较小数,并取余数r。
2. 若r为0,则较小数即为最大公约数。
3. 若r不为0,则用较小数除以r,并取余数r1。
4. 若r1为0,则r即为最大公约数。
5. 若r1不为0,则继续用r除以r1,取余数r2,以此类推,直到余数为0。
最小公倍数可以通过公式lcm(a,b) = a*b/gcd(a,b)求得。
因此,我们可以编写以下代码来求出最大公约数和最小公倍数:
```python
def gcd(a, b):
while b:
a, b = b, a % b
return a
def lcm(a, b):
return a * b // gcd(a, b)
a = 30
b = 45
print("最大公约数:", gcd(a, b))
print("最小公倍数:", lcm(a, b))
```
输出结果为:
```
最大公约数: 15
最小公倍数: 90
```
相关问题
用c语言循环结构求最大公约数和最小公倍数
以下是使用C语言循环结构求最大公约数和最小公倍数的代码示例:
```c
#include <stdio.h>
int main()
{
int num1, num2, i, gcd, lcm;
printf("请输入两个正整数:\n");
scanf("%d %d", &num1, &num2);
// 求最大公约数
i = 1;
while (i <= num1 && i <= num2)
{
if (num1 % i == 0 && num2 % i == 0)
{
gcd = i;
}
i++;
}
// 求最小公倍数
lcm = num1 * num2 / gcd;
printf("%d和%d的最大公约数是%d\n", num1, num2, gcd);
printf("%d和%d的最小公倍数是%d\n", num1, num2, lcm);
return 0;
}
```
求最大公约数和最小公倍数循环结构python语言
以下是使用循环结构计算最大公约数和最小公倍数的Python代码:
# 计算最大公约数
def gcd(a, b):
while b:
a, b = b, a % b
return a
# 计算最小公倍数
def lcm(a, b):
return a * b // gcd(a, b)
# 测试
num1 = 12
num2 = 18
print("最大公约数为:", gcd(num1, num2))
print("最小公倍数为:", lcm(num1, num2))