首页 > 文章列表 > C程序实现欧几里得算法

C程序实现欧几里得算法

实现 C程序 欧几里得算法
501 2023-09-07

问题

实现欧几里得算法来查找两个整数的最大公约数 (GCD) 和最小公倍数 (LCM),并将结果与​​给定整数一起输出。< /p>

解决方案

实现欧几里得算法求两个整数的最大公约数 (GCD) 和最小公倍数 (LCM) 的解决方案如下 -

< p>求 GCD 和 LCM 的逻辑如下 -

if(firstno*secondno!=0){
   gcd=gcd_rec(firstno,secondno);
   printf("

The GCD of %d and %d is %d

",firstno,secondno,gcd);    printf("

The LCM of %d and %d is %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) -< /p>

 现场演示

#include<stdio.h>
int gcd_rec(int,int);
void main(){
   int firstno,secondno,gcd;
   printf("Enter the two no.s to find GCD and LCM:");
   scanf("%d%d",&firstno,&secondno);
   if(firstno*secondno!=0){
      gcd=gcd_rec(firstno,secondno);
      printf("

The GCD of %d and %d is %d

",firstno,secondno,gcd);       printf("

The LCM of %d and %d is %d

",firstno,secondno,(firstno*secondno)/gcd);    }    else       printf("One of the entered no. is zero:Quitting

");    }    /*Function for Euclid's Procedure*/    int gcd_rec(int x, int y){    if (y == 0)       return x;    return gcd_rec(y, x % y); }

输出

当执行上述程序时,会产生以下结果 -

Enter the two no.s to find GCD and LCM:4 8

The GCD of 4 and 8 is 4

The LCM of 4 and 8 is 8