笨鳥

    問題敘述如下：
    “2520是最小的數(shù)能夠整除1到10，求能被1到20所整除的最小的數(shù)？”
  代碼如下：

/** *//**
     * 數(shù)字i從m到n，遍歷，如果i不能被result整除，我們就將i除以i與result的最大公約數(shù)，并與當(dāng)前result想乘
     *
     */
    private static int getNumber(int m, int n) {
        int result = n;
        for (int i = n - 1; i >= m; i--) {
            if (result % i != 0) {
                result *= i/gcd(result,i);
            }
        }
        return result;
    }

    /** *//**
     * 最大公約數(shù)：歐幾里德算法 定理：gcd(a,b) = gcd(b,a mod b)
     * 
     * @param a
     * @param b
     * @return
     */
    private static int gcd(int a, int b) {
        if (b != 0)
            return gcd(b, a % b);
        else
            return a;
    }

    調(diào)用getNumber(1,20)即可得到答案232792560。
    由于在此用到最大公約數(shù)，所以在下面給出了一些實(shí)現(xiàn)。

    /** *//**
     * 最大公約數(shù)：歐幾里德算法
     * @param a
     * @param b
     * @return
     */
    private static int gcd1(int a, int b) {
        if (a > b) {
            gcd1(b, a);
        }
        int temp = 0;
        for (; b != 0;) {
            temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }

    /** *//**
     * 最大公約數(shù)：Stein算法 gcd(ka,kb) = k gcd(a,b)，也就是最大公約數(shù)運(yùn)算和倍乘運(yùn)算可以交換，
     * 特殊的，當(dāng)k=2時，說明兩個偶數(shù)的最大公約數(shù)必然能被2整除
     * 
     * @param a
     * @param b
     * @return
     */
    private static int gcdByStein(int a, int b) {
        if (a > b) {
            gcdByStein(b, a);
        }
        if (b == 0) {
            return a;
        }
        if (a % 2 == 0 && b % 2 == 0) {
            return 2 * gcdByStein(a / 2, b / 2);//a,b都是偶數(shù)
        }
        if (a % 2 == 0) {
            return gcdByStein(a / 2, b);//僅a為偶數(shù)
        }
        if (b % 2 == 0) {
            return gcdByStein(a, b / 2);//僅b為偶數(shù)
        }
        return gcdByStein((a + b) / 2, (a - b) / 2);//a,b都是奇數(shù)
    }

    如果有其他的方法，也請貼出大家一起討論。^_^
    請不吝賜教。
    @anthor ClumsyBird

-----------------------------
博觀約取，厚積薄發(fā)