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;
    }
}

上一篇
Java经典算法40题 – 题目7 Java经典算法40题 – 题目7
【程序7】题目:输入一行字符,分别统计出其中英文字母、空格、数字和其它字符的个数。思路:逐个读吧。 package org.sixlab.algorithm40; import java.util.HashMap; import java
2014-05-07
下一篇
Java经典算法40题 – 题目5 Java经典算法40题 – 题目5
【程序5】题目:利用条件运算符的嵌套来完成此题:学习成绩> =90分的同学用A表示,60-89分之间的用B表示,60分以下的用C表示。思路:这也算算法? package org.sixlab.algorithm40; public
2014-04-04