首页 > 其他 > 详细

求最大公约数

时间:2015-12-25 22:22:04      阅读:216      评论:0      收藏:0      [点我收藏+]

1、穷举算法  时间复杂度(O(n))

// 从小到大
public
static int gcd(int m, int n) { int gcd = 1; for (int i = 2; i <= m && i <= n; i++) { if (m % i == 0 && n % i == 0) { gcd = i; } } return gcd; }
// 从大到小
public static int gcd(int m, int n) {
int gcd = 1;
        for (int i = n; i >= 1; i--) {
            if (m % i == 0 && n % i == 0) {
                gcd = i;
                break;
            }
        }
        return gcd;
    }
// 穷举算法  数字n的除数不可能比n/2大
public static int gcd(int m, int n) { int gcd = 1; if (m % n == 0) { return n; } for (int i = n / 2; i >= 1; i--) { if (m % i == 0 && n % i == 0) { gcd = i; break; } } return gcd; }

 

2、递归  时间复杂度(O(logn))

public static int gcd(int m, int n) {

        if (m % n == 0) {
            return n;
        }
        else {
            return gcd(n, m % n);
        }
    }

 3、while循环  时间复杂度(O(logn))

public static int gcd(int m, int n) {

        int remainder = m % n;
        while (remainder > 0) {
            m = n;
            n = remainder;
            remainder = m % n;
        }
        return n;
    }

 

求最大公约数

原文:http://www.cnblogs.com/diyishijian/p/5076962.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!