查找两个数的最大公约数——欧几里得算法

时间:2022-09-08 09:46:44

欧几里得算法:

      百度百科:欧几里德算法又称辗转相除法,是指用于计算两个正整数a,b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

代码实现如下:

import java.util.Scanner;

public class Main 
{
    public static void main(String[] args)
    {
        //这里输入的a,b均是大于0的。
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext())
        {
            int a = cin.nextInt();
            int b = cin.nextInt();
            int c = Math.min(a, b);
            a = Math.max(a, b);
            b = c;
            while(b != 0)
            {
                c = a%b;
                a = b;
                b = c;
            }
            System.out.println(a);
        }
    }
}