1. 輾轉(zhuǎn)相除法

? ? ? ? 輾轉(zhuǎn)相除法又稱歐幾里得算法，求兩個(gè)數(shù)的最大公因數(shù)，希臘數(shù)學(xué)家喜歡用圖形來處理問題，于是將要求最大公約數(shù)問題轉(zhuǎn)化為，以兩個(gè)數(shù)字構(gòu)成矩形，尋找可以鋪滿整個(gè)矩形的最大正方形的邊長問題。

題目

例如8和12的最大公因數(shù)是4，記作gcd(8，12)=4，輾轉(zhuǎn)相除法的規(guī)則是，若r是a%b的余數(shù)，則gcd（a，b）= gcd（b，r）。

計(jì)算gcd（546，429）

思路

?????????希臘數(shù)學(xué)家是這樣處理的，在我們預(yù)先構(gòu)造的矩形中，我們先以矩形的短邊構(gòu)造正方形，然后再去計(jì)算這樣的正方形可以在大矩形中「最多」放置多少個(gè)，這個(gè)計(jì)算過程可以用取余的方式進(jìn)行計(jì)算。接下來，我們再用長邊余下的長度構(gòu)建正方形，在去試圖鋪滿剩下未被覆蓋的部分，然后計(jì)算這個(gè)正方形最多可以放置幾個(gè)，直到我們找到這樣一個(gè)正方形，這個(gè)正方形可以完全鋪滿整個(gè)大矩形。那么這個(gè)正方形就是我們最終要找的答案，自然而然的，這個(gè)正方形的邊長也就是我們要找的兩數(shù)的最大公約數(shù)。

代碼

    /**
     * 輾轉(zhuǎn)相除法
     */
    public int gcd(int a, int b){
        int k = 0;
        do {
            k = a % b;//得到余數(shù)
            a = b;  //根據(jù)輾轉(zhuǎn)相除法，把被除數(shù)賦給除數(shù)
            b = k;  // 余數(shù)賦給被除數(shù)
        }while (k != 0);
        return a; //返回被除數(shù)
    }

2.素?cái)?shù)和合數(shù)

題目

? ? ? ? 素?cái)?shù)又稱質(zhì)數(shù)，大于等于2的數(shù)，只能被1和自己整除的數(shù)是素?cái)?shù)，其余的都是合數(shù)，

要求：給定一個(gè)正整數(shù)n（n<10^9），判斷是否是素?cái)?shù)。

思路

從2開始對n進(jìn)行取余測試，看是否出現(xiàn)n%i==0，如果出現(xiàn)就不是，理論上一直測試到n-1，但我們只需要測試到n^(1/2)，至于為什么，大家可以思考一下，如果大于n^(1/2)中的一個(gè)數(shù)可以被n整數(shù)，其結(jié)構(gòu)必定小于n^(1/2)，這個(gè)數(shù)會(huì)被提前找到。

代碼

    /**
     * 素?cái)?shù)和合數(shù)
     */
    public boolean isPrime(int num){
        int max = (int) Math.sqrt(num);
        for (int i = 2; i < max; i++) {
            if (num % i == 0){
                return false;
            }
        }
        return true;
    }

拓展

Leetcode中的204題，用埃氏篩的方法來找素?cái)?shù)，找到一個(gè)數(shù)，就把這個(gè)數(shù)的整數(shù)倍的數(shù)全部排除，排除完之后白色方塊中剩余的就是素?cái)?shù)，下面只是例子，并沒有排除完，

選中2是素?cái)?shù)，將2的倍數(shù)的數(shù)都排除（代碼中將數(shù)組的位置標(biāo)記為0）

選中3是素?cái)?shù)，將3的倍數(shù)的數(shù)都排除

選中5是素?cái)?shù)，將5的倍數(shù)的數(shù)都排除

代碼2

    /**
     * 埃氏篩
     */
    public int countPrimes(int n){
        int[] isPrime = new int[n];
        Arrays.fill(isPrime,1);
        int ans = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i] == 1){
                ans += 1;
                if ((long) i * i < n){
                    for (int j = i * i; j < n; j++) {
                        isPrime[j] = 0;
                    }
                }
            }
        }
        return ans;
    }

4. 丑數(shù)問題

題目

把質(zhì)因子2、3和5的數(shù)稱為丑數(shù)，按照從小到大的順序輸出第n個(gè)丑數(shù)

思路

若n是丑數(shù)，n可以寫成n=2^a + 3^b + 5^c的形式，n反復(fù)除以2，3，5，若最后是1，則證明是丑數(shù)文章來源地址http://www.zghlxwxcb.cn/news/detail-699969.html

代碼

    /**
     * 丑數(shù)問題
     */
    public boolean isUgly(int n){
        if (n <= 0){
            return false;
        }
        int[] factors = {2,3,5};
        for (int factor:factors
             ) {
            while (n % factor == 0){
                n /= factor;
            }
        }
        return n == 1;
    }

到了這里，關(guān)于算法通關(guān)村十三關(guān) | 輾轉(zhuǎn)相除法、素?cái)?shù)和丑數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！