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.
reference Euclidean algorithm and indefinite equation | Beautiful story of high school mathematics
package com.company;
import java.io.*;
class Main {
public static void main(String[] args) {
try {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String[] str = bufferedReader.readLine().split(" ");
int x = Integer.parseInt(str[0]);
int y = Integer.parseInt(str[1]);
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;
}
}
//input
390 273
//output
39
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".
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);
readInput();
System.out.println(doEuclideanAlgorithm(x, y));
}
private static void readInput() {
try {
while (x <= 0 || y <= 0) {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String[] str = bufferedReader.readLine().split(" ");
x = Integer.parseInt(str[0]);
y = Integer.parseInt(str[1]);
if (x <= 0 || y <= 0) {
System.out.println("The input is incorrect." + caution);
}
}
} catch (Exception e) {
System.out.println("The input is incorrect." + caution);
readInput();
}
}
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;
}
}
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
If you have something like "It's strange here" or "I can make it smarter", I would appreciate it if you could comment.
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.
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);
int[] inputs = readInput();
System.out.println(doEuclideanAlgorithm(inputs[0], inputs[1]));
}
private static int[] readInput() {
try {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String[] str = bufferedReader.readLine().split(" ");
int x = Integer.parseInt(str[0]);
int y = Integer.parseInt(str[1]);
if (x <= 0 || y <= 0) {
throw new Exception("");
}
return new int[]{x, y};
} catch (Exception e) {
System.out.println("The input is incorrect." + caution);
return readInput();
}
}
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;
}
}
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
Euclidean algorithm and indefinite equation | Beautiful story of high school mathematics
Recommended Posts