解题思路:
欧几里得算法是用来求两个正整数最大公约数的算法,也称辗转相除法。古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法。
扩展欧几里得算法可用于RSA加密等领域。
假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法,是这样进行的:
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此,最大公约数为1
以除数和余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数,所以就得出了 1997 和 615 的最大公约数 1。
注意事项:
参考代码:
#include
int main()
{
int a,b,n,z;
scanf("%d%d", &a, &b);
n=a*b;
while(b!=0){
z=a%b;
a=b;
b=z;
}
printf("%d%d",a,n/a);
return 0;
}
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:612 |
printf基础练习2 (C语言代码)浏览:942 |
C语言训练-大、小写问题 (C语言代码)浏览:724 |
wu-理财计划 (C++代码)浏览:833 |
C语言考试练习题_保留字母 (C语言代码)浏览:703 |
母牛的故事 (C语言代码)浏览:549 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:552 |
模拟计算器 (C语言代码)浏览:2299 |
输出九九乘法表 (C语言代码)浏览:1048 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:584 |