C 程序实现欧几里得算法
cserver side programmingprogramming更新于 2024/11/9 16:37:00
问题
实现欧几里得算法，找出两个整数的最大公约数 (GCD) 和最小公倍数 (LCM)，并将结果与给定的整数一起输出。
解决方案
实现欧几里得算法，找出两个整数的最大公约数 (GCD) 和最小公倍数 (LCM) 的解决方案如下 −
查找 GCD 和 LCM 的逻辑如下 −
if(firstno*secondno!=0){
gcd=gcd_rec(firstno,secondno);
printf("
%d 与 %d 的最大公约数为 %d
",firstno,secondno,gcd);
printf("
%d 与 %d 的最小公倍数为 %d
",firstno,secondno,(firstno*secondno)/gcd);
}
调用的函数如下 −
int gcd_rec(int x, int y){
if (y == 0)
return x;
return gcd_rec(y, x % y);
}
程序
以下是 C 程序，用于实现欧几里得算法以查找两个整数的最大公约数 (GCD) 和最小公倍数 (LCM) −
#include<stdio.h>
int gcd_rec(int,int);
void main(){
int firstno,secondno,gcd;
printf("输入两个数字以查找 GCD 和 LCM:");
scanf("%d%d",&firstno,&secondno);
if(firstno*secondno!=0){
gcd=gcd_rec(firstno,secondno);
printf("
%d 和 %d 的最大公约数是 %d
",firstno,secondno,gcd);
printf("
%d 和 %d 的最小公倍数是 %d
",firstno,secondno,(firstno*secondno)/gcd);
}
else
printf("输入的数字中有一个为零:退出
");
}
/*欧几里得程序函数*/
int gcd_rec(int x, int y){
if (y == 0)
return x;
return gcd_rec(y, x % y);
}
输出
当执行上述程序时，它会产生以下结果 −
输入两个数字来查找 GCD 和 LCM:4 8 4 和 8 的最大公约数是 4 4 和 8 的最小公倍数是 8
