HCF(Highest Common Factor) or GCD -Greatest Common Divisor

கொடுக்கப்பட்டுள்ள அனைத்து number-ஐயும் பொதுவாக divide செய்யகூடிய எண்களில் பெரிய எண் GCD என்று அழைக்கபடுகிறது. உதாரணதிற்கு 10,20 இந்த இரண்டு எண்களை எடுத்துகொண்டால் 2,5,10 இந்த 3 எண்களும், 10 மற்றும் 20 common-ஆக divide செய்கின்றது. இந்த மூன்றில் பெரிய எண் 10. இதுவே 10,20-இன் GCD ஆகும்.

Euclid's algorithm-ம் படி, number1 மற்றும் number2 எடுத்துகொள்வோம். இதில் number2=0 ஆக இருந்தால் number1-தான் இரண்டு number-க்கும் GCD. ஒருவேலை number2 !=0 ஆக இருந்தால் number2-ன் value-ஐ number1-க்கு மாற்றிவிட்டு அதாவது number1=number2. இப்பொழுது number2-ன் value-ஐ number2= number1%number2; என்று மாற்றி விடவேண்டும். இபொழுது number2-ன் value 0-ஆக இருக்கின்றதா என்று மீண்டும் சரிபார்க்க வேண்டும். இருந்தால் number1-ன் value GCD-ஆக கருதப்படும். இல்லையனில் மீண்டும் மீண்டும் number1 மற்றும் number2-ன் value-ஐ மாற்றிக்கொண்டே இருக்கவேண்டும் number2-ன் value 0 ஆகும் வரை.

இதற்க்கு getGCD(number2, number1 % number2) என்ற recursive function-ஐ பணடுதுக்கின்றோம்.

Program to find GCD

#include<iostream.h>
#include<conio.h>
int main(){
 int number1,number2,gcd;
  cout<<"\nEnter number1: ";
  cin>>number1;
  cout<<"\nEnter number2: ";
  cin>>number2;
  // function call
  gcd=getGCD(number1, number2);
  cout<<"GCD is : "<<gcd;
  return 0;
}

int getGCD(int number1, int number2) {
    if (number2 == 0) {
        return number1;
    }
    // recursive function call
    return getGCD(number2, number1 % number2);
}

Program to find GCD and LCM

கொடுக்கப்பட்டுள்ள இரண்டு number-ஐ பெருக்கி(multiply) GCD-ஆல் divide செய்த பின் கிடைக்கும் value LCM என்று அழைக்கபடுகிறது

#include<iostream.h>
#include<conio.h>
int main(){
  int number1,number2,temp,a,b,gcd,lcm;
  cout<<"Enter number1: ";
  cin>>number1;
  cout<<"Enter number2: ";
  cin>>number2;
  a = number1;
  b = number2;
  while (b != 0){
    temp = b;
    b = a % b;
    a = temp;
  }
  gcd = a;
  lcm = (number1*number2)/gcd;
  cout<<"\nGCD is: "<<gcd;
  cout<<"\nLCM is: "<<lcm;         
return 0;
}