欧几里得算法
package euclidean_algorithm; import java.util.Scanner; /** * @author ALazy_cat * 欧几里得算法的自然语言描述: * 计算两个非负整数x和y的最大公约数: 若y = 0,则最大公约数为x; 否则将remainder = x % y,x和y的 * 最大公约数即为y和remainder的最大公约数 */ public class EuclideanAlgorithm { public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.print("请输入两个整数: "); int x = 0, y = 0; x = in.nextInt(); y = in.nextInt(); System.out.println("x, y的最大公约数是: " + euclideanAlgorithm_01(x, y, 1)); System.out.println("---------------------"); System.out.println("x, y的最大公约数是: " + euclideanAlgorithm_02(x, y, 1)); } //欧几里得算法的递归实现 public static int euclideanAlgorithm_01(int x, int y, int count) { //当y = 0时,递归结束 int remainder = 0; System.out.println("第" + count++ + "次递归: " + "x = " + x + " , " + "y = " + y); if (y == 0) return x; remainder = x % y; return euclideanAlgorithm_01(y, remainder, count); } //欧几里得算法的循环实现 public static int euclideanAlgorithm_02(int x, int y, int count) { int remainder = 0; while (y != 0) { System.out.println("第" + count++ + "次循环: " + "x = " + x + " , " + "y = " + y); remainder = x % y; x = y; y = remainder; } System.out.println("第" + count++ + "次循环: " + "x = " + x + " , " + "y = " + y); return x; } }