[GO] 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

a=bq + r

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

Recommended Posts

Find the greatest common divisor and least common multiple with JAVA
Find the greatest common divisor and least common multiple of any number of integers in Ruby
Find the address class and address type from the IP address with Java
Find the address class and address type from the IP address with Java [No. 2 decoction]
Sample source code for finding the least common multiple of multiple values in Java
Prepare the environment for java11 and javaFx with Ubuntu 18.4
[Java] Development with multiple files using package and import
Difference between Java and JavaScript (how to find the average)
[Java] Check the difference between orElse and orElseGet with IntStream
I want to return to the previous screen with kotlin and java!
Use java with MSYS and Cygwin
Distributed tracing with OpenCensus and Java
Use JDBC with Java and Scala.
Follow the link with Selenium (Java)
Output PDF and TIFF with Java 8
Encrypt with Java and decrypt with C #
[Java] Create a jar file with both compressed and uncompressed with the jar command
Find the maximum and minimum of the five numbers you entered in Java
<java> Split the address before and after the street address with a regular expression
Monitor Java applications with jolokia and hawtio
Link Java and C ++ code with SWIG
Let's try WebSocket with Java and javascript!
[Java] Reading and writing files with OpenCSV
How to find the tens and ones
[Java 7] Divide the Java list and execute the process
[Java8] Search the directory and get the file
Find the difference from a multiple of 10
Try using the Wii remote with Java
[Java] Get the date with the LocalDateTime class
Be careful with requests and responses when using the Serverless Framework in Java