Find the greatest common divisor and least common multiple with JAVA

Introduction

Create a JAVA program to find the greatest common divisor and least common multiple.

algorithm

The algorithm for finding the greatest common divisor and the least common multiple is explained.

Greatest common divisor

The greatest common divisor is calculated by Euclidean algorithm. In Euclidean algorithm, the equation of division

In, the greatest common divisor of $ a $ and $ b $ is calculated using the property that it is equal to the greatest common divisor of $ r $ and $ b $. (Reference: Beautiful story of high school mathematics)

The procedure to obtain is as follows. (Reference: Example program for finding the greatest common divisor)

For two natural numbers a and b (a> = b)

1. Substitute the remainder of dividing a by b into r
2. If r = 0, b becomes the greatest common divisor and processing ends.
3. Substitute b for a, substitute r for b, and return to 1.

Computational complexity is $ O (\ log (\ min (a, b)) $

Least common multiple

The least common multiple $ lcm $ of the two natural numbers $ a $ and $ b $ is calculated by the following equation, where the greatest common divisor of $ a $ and $ b $ is $ gcd . (See: [Algorithm for finding the least common multiple (LCM) of two natural numbers](https://algo-logic.info/lcm/)) $ lcm = \frac{a\times b}{gcd} $$ Computational complexity is $ O (\ log (\ min (a, b)) $

Implementation

The implemented program is as follows.

Euclid.java

public class Euclid{
    public static int gcd(int a,int b){
        if(a <= 0 || b <= 0){
            return -1;
        }
        else if(a < b){
            int tmp = a;
            a = b;
            b = tmp;
        }
        
        if(a % b == 0)
            return b;
        else
            return gcd(b,a%b);
    }

    public static int lcm(int a,int b){
        return a / gcd(a,b) * b;
    }
}

EuclidMain.java

import java.util.Scanner;

public class EuclidMain{
    public static void main(String[] args){
    	Scanner scan = new Scanner(System.in);
    	System.out.println("Input 2 natural numbers.");
    	int a = scan.nextInt();
    	int b = scan.nextInt();
    	System.out.println("Greatest common divisor.");
    	System.out.println(Euclid.gcd(a,b));
    	System.out.println("Least common multiple.");
    	System.out.println(Euclid.lcm(a,b));
    }
}

Execution example

>javac EuclidMain.java
>java EuclidMain
Input 2 natural numbers.
12 9
Greatest common divisor.
3
Least common multiple.
36

reference

-Euclidean algorithm and indefinite equation | Beautiful story of high school mathematics

• Program for finding the greatest common divisor Euclidean algorithm and recursive call|C language tips|C language introductory course clip -Algorithm for finding the least common multiple (LCM) of two natural numbers | Algorithm logic