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); } } }