โปรแกรม C เพื่อใช้อัลกอริทึมของ Euclid

ปัญหา

ใช้อัลกอริธึมของ Euclid เพื่อค้นหาตัวหารร่วมมาก (GCD) และตัวคูณร่วมน้อย (LCM) ของจำนวนเต็มสองตัวและเพื่อแสดงผลผลลัพธ์พร้อมกับจำนวนเต็มที่กำหนด

วิธีแก้ปัญหา

วิธีแก้ปัญหาในการใช้อัลกอริทึมของ Euclid เพื่อค้นหาตัวหารร่วมมาก (GCD) และตัวคูณร่วมน้อย (LCM) ของจำนวนเต็มสองตัวมีดังนี้ -

ตรรกะที่ใช้ในการค้นหา GCD และ LCM มีดังนี้ -

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);
}

ฟังก์ชันที่เรียกมีดังต่อไปนี้ −

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("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);
}

ผลลัพธ์

เมื่อโปรแกรมข้างต้นทำงาน มันจะให้ผลลัพธ์ดังต่อไปนี้ −

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