Euclidean Algorithm implementation written in Java.

Subtraction-based version:

Iteration version:

import java.util.Scanner;

// © 2017 TheFlyingKeyboard and released under MIT License
// theflyingkeyboard.net

public class GCD {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int number1;
        int number2;
        
        System.out.print("Enter first number: ");
        number1 = input.nextInt();
        
        System.out.print("Enter second number: ");
        number2 = input.nextInt();
        
        System.out.println("GCD of " + number1 + " and " + number2 + " is equal to " + gcd(number1, number2));
    }
    
  static int gcd(int a, int b){
    while(a != b){
      if(a > b){
        a = a - b;
      }else{
        b = b - a;
      }
    }
    
    return a;
  }
}

Recursive version:

import java.util.Scanner;
 
// © 2017 TheFlyingKeyboard and released under MIT License
// theflyingkeyboard.net

public class GCD {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int number1;
        int number2;
        
        System.out.print("Enter first number: ");
        number1 = input.nextInt();
        
        System.out.print("Enter second number: ");
        number2 = input.nextInt();
        
        System.out.println("GCD of " + number1 + " and " + number2 + " is equal to " + gcd(number1, number2));
    }
    
  static int gcd(int a, int b){
    if(a > b){
        return gcd(a - b, b);
      }else if(a < b){
        return gcd(a, b - a);
      }else{
        return a;
      } 
    }
}

Division-based version:

Iteration version:

import java.util.Scanner;

// © 2017 TheFlyingKeyboard and released under MIT License
// theflyingkeyboard.net

public class GCD {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int number1;
        int number2;
        
        System.out.print("Enter first number: ");
        number1 = input.nextInt();
        
        System.out.print("Enter second number: ");
        number2 = input.nextInt();
        
        System.out.println("GCD of " + number1 + " and " + number2 + " is equal to " + gcd(number1, number2));
    }
    
  static int gcd(int a, int b){
    int t;
    
    while(b != 0){
      t = b;
      b = a % b;
      a = t;
    }
    
    return a;
  }
}

Recursive version:

import java.util.Scanner;

// © 2017 TheFlyingKeyboard and released under MIT License
// theflyingkeyboard.net

public class GCD {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int number1;
        int number2;
        
        System.out.print("Enter first number: ");
        number1 = input.nextInt();
        
        System.out.print("Enter second number: ");
        number2 = input.nextInt();
        
        System.out.println("GCD of " + number1 + " and " + number2 + " is equal to " + gcd(number1, number2));
    }
    
  static int gcd(int a, int b){
    if(b == 0){
        return a;
      }
      else{
        return gcd(b, a % b);
      }
    }
}

 

Java Euclidean Algorithm
Tagged on:     

Leave a Reply

Your email address will not be published. Required fields are marked *