C++ program to find the GCD or HCF of two numbers
Program to find the GCD or HCF of two numbers
Here we will discuss how to find the GCD or HCF of two numbers entered by the user using C++ programming language.
GCD i.e. Greatest Common Divisible or HCF i.e. Highest Common Factor of two numbers is the largest positive integer that can divide both the numbers
There are many methods to calculate GCD:
- Using Prime Factorisation,
- Euclid’s Algorithm,
- Lehmer’s GCD algorithm, etc
Here we will use Euclid’s Algorithm to find the GCD, which is based on the idea that the GCD doesn’t change when smaller number is subtracted from the greater number. This keeps on going until only the GCD left.
- Two inputs are taken from the user.
- Inputs are stored in two int type variables say first and second.
- A recursive program findGCD is called with parameters first and second.
- First it is checked whether any of the input is 0
if (first == 0)
2. If both input numbers are equal return any of the two numbers
if (first == second)
3. If first is greater than the second
- Recursively call findGCD function with parameters ‘first-second’, second.
findGCD(first – second, second);
4. Otherwise recursively call findGCD function with parameters ‘first’, ‘second-first’.
findGCD(first, second – first);
- Highest Common Factor(HCF): C | C++ | Java
- Lowest Common Multiple (LCM) : C | C++ | Java
- Greatest Common Divisor : C | C++ | Java
- Binary to Decimal to conversion : C | C++ | Java
- Binary to Octal conversion : C | C++ | Java
- Decimal to Binary conversion: C | C++ | Java
- Decimal to octal Conversion: C | C++ | Java
- Octal to Binary conversion : C | C++ | Java
- Octal to Decimal conversion : C | C++ | Java
- Quadrants in which a given coordinate lies : C | C++ | Java
- Permutations in which n people can occupy r seats in a classroom : C | C++ | Java
- Maximum number of handshakes: C | C++ | Java
- Addition of two fractions: C | C++ | Java
- Replace all 0’s with 1 in a given integer : C | C++ | Java
- Can a number be expressed as a sum of two prime numbers
: C | C++ | Java