Chương trình C để triển khai thuật toán Euclid

Vấn đề

Triển khai thuật toán Euclid để tìm ước chung lớn nhất (GCD) và bội chung nhỏ nhất (LCM) của hai số nguyên và để xuất ra kết quả cùng với các số nguyên đã cho.

Giải pháp

Giải pháp để triển khai thuật toán Euclid để tìm ước số chung lớn nhất (GCD) và bội số chung nhỏ nhất (LCM) của hai số nguyên như sau -

Logic được sử dụng để tìm GCD và LCM như sau -

if(firstno*secondno!=0){
   gcd=gcd_rec(firstno,secondno);
   printf("\nThe GCD of %d and %d is %d\n",firstno,secondno,gcd);
   printf("\nThe LCM of %d and %d is %d\n",firstno,secondno,(firstno*secondno)/gcd);
}

Hàm được gọi như sau -

int gcd_rec(int x, int y){
   if (y == 0)
      return x;
   return gcd_rec(y, x % y);
}

Chương trình

Sau đây là chương trình C để triển khai thuật toán Euclid để tìm ước số chung lớn nhất (GCD) và bội số chung nhỏ nhất (LCM) của hai số nguyên -

#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("\nThe GCD of %d and %d is %d\n",firstno,secondno,gcd);
      printf("\nThe LCM of %d and %d is %d\n",firstno,secondno,(firstno*secondno)/gcd);
   }
   else
      printf("One of the entered no. is zero:Quitting\n");
   }
   /*Function for Euclid's Procedure*/
   int gcd_rec(int x, int y){
   if (y == 0)
      return x;
   return gcd_rec(y, x % y);
}

Đầu ra

Khi chương trình trên được thực thi, nó tạo ra kết quả sau -

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