# I tried to implement the Euclidean algorithm in Java

## What is Euclidean algorithm?

An algorithm that finds the greatest common divisor of two natural numbers.

To put it simply

``````a % b = r
b % r = s
r % s = 0
``````

The number to be divided is the next number to be divided, and the remainder is the next number to be divided, and this is repeated recursively. The number to divide when the remainder becomes 0 (s in the above example) is the greatest common divisor of the natural numbers a and b.

## I tried to implement

``````package com.company;

import java.io.*;

class Main {
public static void main(String[] args) {
try {
int x = Integer.parseInt(str);
int y = Integer.parseInt(str);

System.out.println(getCommonDivisor(x, y));

} catch (Exception e) {
System.out.println(e);
}
}

private static int getCommonDivisor(int x, int y) {
int biggerNum = Math.max(x, y);
int smallerNum = Math.min(x, y);

//Find the remainder of dividing the smaller one from the larger one
int surplus = biggerNum % smallerNum;

//If it is divisible, return it
if (surplus == 0) {
return smallerNum;
}
//Recursively call confidence if not divisible
surplus = getCommonDivisor(smallerNum, surplus);

return surplus;
}
}
``````

## Try out

``````//input
390 273

//output
39
``````

## Postscript (June 23, 2017)

The above code originally did not think deeply about input etc., just implemented the algorithm, so it does not consider exception handling etc. and it easily falls.

Therefore, I wrote a new code that reflects the comment received from @ saka1029. Thank you, @ saka1029.

This time, the code is written under the following conditions.

With the implementation of Euclidean algorithm, negative numbers are repelled at the entrance.

Even if something other than numbers is entered, it will not drop

In addition, there are schools that include 0 in natural numbers and schools that do not include 0 in natural numbers, but this time, we will adopt the "school that does not include 0 in natural numbers".

### Exception handling code

``````package com.company;

import java.io.*;

class Main {
private static int x = -1;
private static int y = -1;
private static final String caution = "Please enter two natural numbers separated by half-width spaces.(However, 0 is not naturally included in this program.)";

public static void main(String[] args) {
System.out.println(caution);
System.out.println(doEuclideanAlgorithm(x, y));
}

try {
while (x <= 0 || y <= 0) {
x = Integer.parseInt(str);
y = Integer.parseInt(str);
if (x <= 0 || y <= 0) {
System.out.println("The input is incorrect." + caution);
}
}
} catch (Exception e) {
System.out.println("The input is incorrect." + caution);
}
}

private static int doEuclideanAlgorithm(int x, int y) {
int biggerNum = Math.max(x, y);
int smallerNum = Math.min(x, y);

//Find the remainder of dividing the smaller one from the larger one
int surplus = biggerNum % smallerNum;

//If it is divisible, return it
if (surplus == 0) {
return smallerNum;
}
//Recursively call confidence if not divisible
surplus = doEuclideanAlgorithm(smallerNum, surplus);

return surplus;
}
}
``````

### I've tried

``````Please enter two natural numbers separated by half-width spaces.(However, 0 is not naturally included in this program.)
a a
The input is incorrect. Please enter two natural numbers separated by half-width spaces.(However, 0 is not naturally included in this program.)
390 0
The input is incorrect. Please enter two natural numbers separated by half-width spaces.(However, 0 is not naturally included in this program.)
0 273
The input is incorrect. Please enter two natural numbers separated by half-width spaces.(However, 0 is not naturally included in this program.)
-390 273
The input is incorrect. Please enter two natural numbers separated by half-width spaces.(However, 0 is not naturally included in this program.)
390 -273
The input is incorrect. Please enter two natural numbers separated by half-width spaces.(However, 0 is not naturally included in this program.)
390 273
39
``````

### Other

If you have something like "It's strange here" or "I can make it smarter", I would appreciate it if you could comment.

## Further notes (June 23, 2017)

As you said in @ howdy39's comment, there were some subtleties. Thank you, @ howdy39. Here is the smart code that adopted @ howdy39's point.

I didn't need a while statement because I was recursively executing readInput () when there was an exception.

### Implementation

``````package com.company;

import java.io.*;

class Main {
private static final String caution = "Please enter two natural numbers separated by half-width spaces.(However, 0 is not naturally included in this program.)";

public static void main(String[] args) {
System.out.println(caution);
System.out.println(doEuclideanAlgorithm(inputs, inputs));
}

try {
int x = Integer.parseInt(str);
int y = Integer.parseInt(str);
if (x <= 0 || y <= 0) {
throw new Exception("");
}
return new int[]{x, y};
} catch (Exception e) {
System.out.println("The input is incorrect." + caution);
}
}

private static int doEuclideanAlgorithm(int x, int y) {
int biggerNum = Math.max(x, y);
int smallerNum = Math.min(x, y);

//Find the remainder of dividing the smaller one from the larger one
int surplus = biggerNum % smallerNum;

//If it is divisible, return it
if (surplus == 0) {
return smallerNum;
}
//Recursively call confidence if not divisible
surplus = doEuclideanAlgorithm(smallerNum, surplus);

return surplus;
}
}
``````

### Execution result

``````Please enter two natural numbers separated by half-width spaces.(However, 0 is not naturally included in this program.)
a a
The input is incorrect. Please enter two natural numbers separated by half-width spaces.(However, 0 is not naturally included in this program.)
390 0
The input is incorrect. Please enter two natural numbers separated by half-width spaces.(However, 0 is not naturally included in this program.)
0 273
The input is incorrect. Please enter two natural numbers separated by half-width spaces.(However, 0 is not naturally included in this program.)
-390 273
The input is incorrect. Please enter two natural numbers separated by half-width spaces.(However, 0 is not naturally included in this program.)
390 -273
The input is incorrect. Please enter two natural numbers separated by half-width spaces.(However, 0 is not naturally included in this program.)
390 273
39
``````

## The site that I used as a reference

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

• The same post is posted on the blog [I implemented the mutual division method of Eugrid in Java](http://www.sekky0905.com/entry/2017/06/22/Java%E3%81%A7%E3%83%A6%E3%83 % BC% E3% 82% B0% E3% 83% AA% E3% 83% 83% E3% 83% 89% E3% 81% AE% E4% BA% 92% E9% 99% A4% E6% B3% 95 % E3% 82% 92% E5% AE% 9F% E8% A3% 85% E3% 81% 97% E3% 81% A6% E3% 81% BF% E3% 81% 9F)