Program to find HCF of two numbers

In this post, you will learn how to write program to find the highest common factor (H.C.F.) or greatest common divisor (G.C.D) of two numbers in different programming languages. Such a type of question is generally asked in programming interviews.

The greatest common divisor (G.C.D) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers a, b, the greatest common divisor of a and b is denoted gcd(a,b).

Java program to find HCF of two numbers using for loop

Here, we define a function to compute the G.C.D of two numbers, x and y, and return it. In each iteration, we check if our number perfectly divides both the given numbers. If this is true, we store the number as H.C.F. At the completion of the loop, we conclude with the largest number that perfectly divides both the numbers.

public class GetGCD   
{  
    public static void main(String[] args)   
    {  
    // defining variables
    int x = 4, y = 10, gcd = 1;  
    
    // iterate form 1 to the smallest of both numbers  
    for(int i = 1; i <= x && i <= y; i++)  
    {  
        
        if(x%i==0 && y%i==0)  
        
        gcd = i;  
    }  
    //prints the gcd  
    System.out.printf("GCD of %d and %d is: %d", x, y, gcd);  
    }  
}

Output of the above code:

GCD of 4 and 10 is: 2

Java program to find HCF of two numbers using Euclidean algorithm

The Euclidean algorithm is an efficient way to find the greatest common divisor of two numbers, the largest number that divides them both without a remainder.

import java.util.Scanner;  
public class ComputeGCD  
{  
  public static void main(String args[])  
  {  
    Scanner sc = new Scanner(System.in);  
    System.out.println("Please enter the first number: ");  
    int x = sc.nextInt();     
    System.out.println("Please enter the second number: ");  
    int y = sc.nextInt(); 
    
    System.out.println("GCD of " + x + " and " + y + " =  " + findGCD(x,y));  
  }  
  static int findGCD(int x, int y)  
  {  
    int g=0, a, b;  
    
    // a is greater number  
    a = (x > y) ? x : y; 
    
    // b is smaller number  
    b = (x < y) ? x : y; 
    g = b;  
    while(a % b != 0)  
    {  
    g = a % b;  
    a = b;  
    b = g;  
    }  
    return g;  
  }  
}

Output of the above code:

Please enter the first number: 15
Please enter the second number: 25
GCD of 15 and 25 =  5

Python program to find HCF of two numbers using math.gcd() Method

In Python, the math module contains various mathematical functions, which can be performed effortlessly utilising the module. The math.gcd() method computes the greatest common divisor of two numbers.

math.gcd(x, y)

Here, x and y are non negative integers for computing GCD. It returns a positive integer value representing the greatest common divisor (GCD) of two integers.

import math

# Greatest common divisor of the two integers
print("GCD of (5, 2) = ",math.gcd(5, 2))
print("GCD of (4, 10) = ",math.gcd(4, 10))
print("GCD of (10, 0) = ",math.gcd(10, 0))
print("GCD of (-9, -16) = ",math.gcd(-9, -16))
print("GCD of (4, 14) = ",math.gcd(4, 14))
print("GCD of (6, 3) = ",math.gcd(6, 3))

Output of the above code:

GCD of (5, 2) =  1
GCD of (4, 10) =  2
GCD of (10, 0) =  10
GCD of (-9, -16) =  1
GCD of (4, 14) =  2
GCD of (6, 3) =  3

C program to find HCF of two numbers using for loop

In the given example, we have used the C program to find the two numbers using a for loop. First, we take two numbers from the user and store them in variables num1 and num2. Then, we find the minimum between the given two numbers and run the for loop from 1 to the minimum value. Inside the loop, we check if i is a factor of two numbers, then set i as HCF, i.e., gcd = i.

#include<stdio.h>  

int main()  
{  
    int num1, num2, i, gcd;  
    printf ( " Enter any two numbers: \n ");  
    scanf ( "%d %d", &num1, &num2);   
      
    for( i = 1; i <= num1 && i <= num2; ++i)  
    {  
        if (num1 % i ==0 && num2 % i == 0)  
            gcd = i; 
    }  
    // print the GCD of two numbers  
    printf (" GCD of two numbers %d and %d is %d.", num1, num2, gcd);  
    return 0;  
}

Output of the above code:

Enter any two numbers: 
24 42
GCD of two numbers 24 and 42 is 6.

C++ program to find HCF of two numbers using while loop

In the given example, we have used the while loop to find the HCF of two numbers using C++ programming.

#include <iostream>  
using namespace std;  

int main() {
  int num1, num2;

  cout << "Enter two numbers: ";
  cin >> num1 >> num2;
  
  while(num1 != num2) {
    if(num1 > num2)
      num1 -= num2;
    else
      num2 -= num1;
  }

  cout << "HCF = " << num1;
  
  return 0;
}

Output of the above code:

Enter two numbers: 54 62
HCF = 2

Java program to find area of triangle
Area of circle program in Java
Remove duplicate elements from array in Java
Capitalize first letter of each word Java
Convert binary to decimal in Java
Convert array to list Python
Python take screenshot of specific window
Web scraping Python BeautifulSoup
Check if two strings are anagrams Python
Python program to add two numbers
Print new line python
Prime factors of a number in c
Armstrong number program in c
Write a program to check leap year in c
C program to find area of rectangle
C program to convert celsius to fahrenheit
Fibonacci series program in C using recursion
Write a program to find area of circle in C
C program to convert Decimal to Octal
C program to convert decimal to binary
C program to check whether a number is even or odd