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

import java.util.Scanner;

public class GCDExample {

    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter number1: ");
        int number1 = scanner.nextInt();
        System.out.print("Enter number2: ");
        int number2 = scanner.nextInt();
        int gcd=getGCD(number1, number2);// function called
        System.out.println("GCD is :" + gcd);
    }

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

}

Program to find GCD and LCM

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

import java.util.Scanner;
public class GCDExample {
  public static void main(String args[]) {
    Scanner scanner = new Scanner(System.in);
    System.out.print("Enter number1: ");
    int number1 = scanner.nextInt();
    System.out.print("Enter number2: ");
    int number2 = scanner.nextInt();
    int a = number1;
    int b = number2;
     while (b != 0){
          temp = b;
          b = a % b;
          a = temp;
     }
     gcd = a;
     lcm = (number1*number2)/gcd;
   System.out.println("GCD is: "+ gcd);
   System.out.println("LCM is: "+lcm);

  }
}