欧几里得算法（辗转相除法）

mwangblog

发布于 2018-08-02 15:52:46

1.5K0

文章被收录于专栏：mwangblogmwangblog

介绍

欧几里得算法，又称辗转相除法，用于计算两个整数的最大公约数。

下面通过一个例子介绍其原理：计算105和24的最大公约数：

105 = 24 x 4 + 9 24 = 9 * 2 + 6 9 = 6 * 1 + 3 6 = 3 * 2 + 0

当余数为0时，可得到最大公约数。105和24的最大公约数是3.

递归版本：

public static int gcd (int p, int q) {
    if (q == 0)     return p;
    else            return gcd (q, p%q);}

循环版本：

public static int gcdLoop (int p, int q) {
    while (q != 0) {
        int rem = p % q;
        p = q;
        q = rem;
    }
    return p;}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2018-07-16，如有侵权请联系 cloudcommunity@tencent.com 删除