Algorithm

  1. Input:

    Accept two integers as input.

  2. Initialization:

  3. Initialize two variables to store the input integers, say num1 and num2.

  4. Algorithm:

    Set a to the larger of num1 and num2, and b to the smaller.
  5. Use a loop to repeatedly update a to b and b to the remainder when dividing a by b, until b becomes 0.
  6. The value of a at this point is the GCD.

  7. Output:

    Print the GCD.

 

Code Examples

#1 Code Example- C++ Programing Find HCF/GCD

Code - C++ Programming

#include <iostream>
using namespace std;

int main() {
  int n1, n2, hcf;
  cout << "Enter two numbers: ";
  cin >> n1 >> n2;

  // swapping variables n1 and n2 if n2 is greater than n1.
  if ( n2 > n1) {   
    int temp = n2;
    n2 = n1;
    n1 = temp;
  }
    
  for (int i = 1; i <=  n2; ++i) {
    if (n1 % i == 0 && n2 % i ==0) {
      hcf = i;
    }
  }

  cout << "HCF = " << hcf;

  return 0;
}
Copy The Code & Try With Live Editor

Output

x
–
+
cmd
Enter two numbers: 16
76
HCF = 4

#2 Code Example- C++ Programing Find GCD/HCF using while loop

Code - C++ Programming

#include <iostream>
using namespace std;

int main() {
  int n1, n2;

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

  cout << "HCF = " << n1;
  
  return 0;
}
Copy The Code & Try With Live Editor

Output

x
–
+
cmd
Enter two numbers: 16
76
HCF = 4
Advertisements

Demonstration

C++ Programing Example to Find GCD-DevsEnv