Description

GCD (Greatest Common Divisor) or HCF (Highest Common Factor) of two
numbers is the largest number that divides both of them. 

A simple solution is to find all prime factors of both numbers, then find intersection
of all factors present in both numbers. Finally return product of elements in the intersection.

C/C++

/* C Program to find HCF using recursion */
//Save it as HcfUsingRecursion.c

#include<stdio.h>
int main(){

    int num1, num2;

    printf("Enter first number : ");
    scanf("%d",&num1);

    printf("Enter second number : ");
    scanf("%d",&num2);

    int hcf = calculateHCF(num1, num2);

    printf("The hcf of %d and %d is %d",num1,num2,hcf);
}

int calculateHCF(int num1, int num2){
    if(num2 != 0) {

        return calculateHCF(num2, num1%num2);
    }else {

        return num1;
    }
}

Input:
Enter first number : 98
Enter second number : 56

Output:
The HCF of 98 and 56 is 14

Java

/* Java Program to find HCF using recursion */
//Save it as HcfUsingRecursion.java

import java.io.*;
import java.util.Scanner;

public class HcfUsingRecursion {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        
        System.out.println("Enter first number : ");
        int num1 = scanner.nextInt();
        
        System.out.println("Enter second number : ");
        int num2 = scanner.nextInt();
        
        int hcf = calculateHCF(num1, num2);
        
        System.out.println("The HCF of "+ num1 + " and " + num2 + " is " + hcf);
    }

    private static int calculateHCF(int num1, int num2) {
        
        if(num2 != 0) {
            
            return calculateHCF(num2, num1%num2);
        }else {
            
            return num1;
        }		 
    }
}

Input:
Enter first number : 
98
Enter second number : 
56

Output:
The HCF of 98 and 56 is 14

Related Programs