Algorithm

  1. Input: Accept two integers, say a and b, as input.

  2. Initialize Variables: Set variables x and y to the values of a and b respectively.

  3. While Loop: Start a loop that continues until y becomes 0.

    • Inside the loop:
      • Set a temporary variable temp to the value of y.
      • Update y to be the remainder of the division x by y.
      • Update x to be the value of temp.

  4. Output: The GCD is the non-zero value of x when the loop terminates.

 

Code Examples

#1 Code Example- Find GCD of two numbers using for loop and if statement

Code - Java Programming

class Main {
  public static void main(String[] args) {

    // find GCD between n1 and n2
    int n1 = 81, n2 = 153;
    
    // initially set to gcd
    int gcd = 1;

    for (int i = 1; i  < = n1 && i <= n2; ++i) {

      // check if i perfectly divides both n1 and n2
      if (n1 % i == 0 && n2 % i == 0)
        gcd = i;
    }

    System.out.println("GCD of " + n1 +" and " + n2 + " is " + gcd);
  }
}
Copy The Code & Try With Live Editor

Output

x
–
+
cmd
GCD of 81 and 153 is 9

#2 Code Example- Find GCD of two numbers using while loop and if else statement

Code - Java Programming

class Main {
  public static void main(String[] args) {

    // find GCD between n1 and n2
    int n1 = 81, n2 = 153;
    
    while(n1 != n2) {
    
      if(n1 > n2) {
        n1 -= n2;
      }
      
      else {
        n2 -= n1;
      }
    }

    System.out.println("GCD: " + n1);
  }
}
Copy The Code & Try With Live Editor

Output

x
–
+
cmd
GCD: 9

#3 Code Example- GCD for both positive and negative numbers

Code - Java Programming

class GCD {
  public static void main(String[] args) {

    int n1 = 81, n2 = -153;

    // Always set to positive
    n1 = ( n1 > 0) ? n1 : -n1;
    n2 = ( n2 > 0) ? n2 : -n2;

    while(n1 != n2) {
        
      if(n1 > n2) {
        n1 -= n2;
      }
      
      else {
        n2 -= n1;
      }
    }
    
    System.out.println("GCD: " + n1);
  }
}
Copy The Code & Try With Live Editor

Output

x
–
+
cmd
GCD: 9
Advertisements

Demonstration

Java Programing Example to Find GCD of two Numbers-DevsEnv