目 录CONTENT

文章目录

808. 最大公约数-欧几里得算法

Gz
Gz
2022-06-30 / 0 评论 / 0 点赞 / 190 阅读 / 621 字 / 正在检测是否收录...

AcWing 808. 最大公约数-欧几里得算法

输入两个整数 aa 和 bb,请你编写一个函数,int gcd(int a, int b), 计算并输出 aa 和 bb 的最大公约数。

输入格式

共一行,包含两个整数 aa 和 bb。

输出格式

共一行,包含一个整数,表示 aa 和 bb 的最大公约数。

数据范围

1≤a,b≤10001≤a,b≤1000

输入样例:

12 16

输出样例:

4

题解:

辗转相除法:
	又名欧几里德算法(Euclidean algorithm),是求最大公约数的一种方法。方法是:用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。那么最后的除数就是这两个数的最大公约数。

例:求 123456 和 7890 的最大公因数。

图:辗转相除过程
答: 123456 和 7890 的最大公因数是 6

img

代码

import java.util.*;

public class Main {
    public static void main(String[] args)throws Exception {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();

        System.out.println(gcd(a, b));

    }

    public static int gcd(int a, int b){
        if (a % b == 0) return b;
        return gcd(b,a%b);
    }
}
0

评论区