package algorithm;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;/** * @author 小悠 */public class 最大公约数 { public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); System.out.print("请输入要约分的第一个数字："); String num1 = reader.readLine(); Integer first = Integer.valueOf(num1); System.out.print("请输入要约分的第二个数字："); String num2 = reader.readLine(); Integer second = Integer.valueOf(num2); boolean in = true; // 判断是否为负数 if (first < 0 || second < 0) { System.out.println("请输入大于0的数"); in = false; } // 将两者中大的数放到first，小的数放到second if (second > first) { int a = first; first = second; second = a; } if (in) { Integer result1 = 更相减损法(first, second); System.out.println("使用更相减损法，求出来的最大公约数为："+result1); Integer result2 = 辗转相除法_jqdbb算法(first, second); System.out.println("使用辗转相除法_jqdbb算法求出来的最大公约数为："+result2); } } private static Integer 更相减损法(Integer first, Integer second) { // 并且判断是否有0，有则返回另一个数，即为最大公约数 if (first == 0 || second == 0) { return first == 0 ? second : first; } // 正常情况 // 可半者半之 int count = 0; while (first % 2 == 0 && second % 2 == 0) { first/=2; second/=2; count++; } // 不可半者，副置分母、子之数，以少减多，更相减损，求其等也 int mid = first - second; while (second != mid) { first = mid > second ? mid : second; second = mid > second ? second : mid;; mid = first - second; } // 以等数约之（最后应该和最开始用2约的相乘） if (count != 0) { return count*2*second; } return second; } private static Integer 辗转相除法_jqdbb算法(Integer first, Integer second) { return second == 0 ? first : 辗转相除法_jqdbb算法(second, first % second); }}
如果有错欢迎评论区指正~