欢迎光临
六楼实验室
网站运行 3004天 | 文章 85 篇 | 分类 15 个 | 标签 54 个

Java经典算法40题 – 题目6

【程序6】题目:
输入两个正整数m和n,求其最大公约数和最小公倍数。

思路:

最大公约数:
方法1:先找出两个数中最小的数字p,然后将i的取值范围设置为:从p到2,循环判断i是否既能被m整除,又能被n整除,是则return i,如果一直没有一个数字满足条件,则返回1。

方法2(代码未实现):先找出两个数中最小的数字p,然后取得数字p的约数列表q,然后将q中的数字从大到小判断能否被n整除,是则return 该数字,否则return 1。

最小公倍数:
先找出两个数中最大的数字p,设置result初始值为1,将i设为:从2到p,逐个判断i能否被m或者n整除,如果能,则result*i,m或n除以i,继续从i到p判断。

package org.sixlab.algorithm40;

public class CommonNumber {
    public static void main(String\[\] args) {
        System.out.println(leastCommonMultiple(70, 100));
        System.out.println(greatestCommonDivisor(70, 100));
    }

    private static int greatestCommonDivisor(int x, int y) {
        int min = Math.min(x, y);
        for (int i = min; i > 1; i--) {
            if (x % i == 0 && y % i == 0) {
                return i;
            }
        }
        return 1;
    }

    private static int leastCommonMultiple(int x, int y) {
        int max = Math.max(x, y);

        int result = 1;
        for (int i = 2; i < max; i++) {
            if (x % i == 0 && y % i == 0) {
                result *= i;
                x /= i;
                y /= i;
                i--;
            } else if (x % i == 0) {
                result *= i;
                x /= i;
                i--;
            } else if (y % i == 0) {
                result *= i;
                y /= i;
                i--;
            }
        }
        return result;
    }
}
赞(0) 打赏
未经允许不得转载:六楼实验室 » Java经典算法40题 – 题目6
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

六楼实验室 · 矿软科技

六楼实验室矿软科技

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

css.php