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;

    }

}