摘要：算法的確有他獨特的魅力。然后我在做這個題的時候，其實也用到了類似質因數分解，只是其實我們可以更好的利用到因數這一個特性。判斷一個數是否是質數質數列表一開始我們認為每一個數都可能是自身的冪線性篩為質數遍歷質數列表為質數的冪

從三月份到現(xiàn)在，大大小小筆試了十幾家公司（主要是因為一直solo code，沒人內推），然后也能感覺到自己的進步把。從編程題只能ac一題到后來的ak。今天面騰訊的時候，面試官還一度懷疑我專門去刷了騰訊的筆試題。因此，我想開始做算法，也就是大家都知道的leetcode啦。其實真的蠻有意思的，建議前途未卜的在校大學生都可以去試一下。。算法的確有他獨特的魅力。這個專欄我打算加進一塊是，把我見到的有意思的算法題給拿出來，跟大家分享交流。

input: n
output: 一個可以被1到n的所有整數整除的最小整數,
        由于整數過大，輸出這個整數對987654321取余的結果

這里給同學提個醒。。再往下直接就是我寫得解題思路了，希望大家可以先自己思考一下這個問題。

我這里先給出一個，我跟別人交流之后，感覺是可以繼續(xù)發(fā)展的想法：

先求1和2的最小公倍數a1， 然后求a1和3的最小公倍數a2，依次類推最后求出的就是一個可以被所有數整除的最小整數

但是這個方法最大的問題就在于，我們求兩個數的最小公倍數的時候，用到的方法非常麻煩，具體大家可以某度質因數分解之類的方法。

然后我在做這個題的時候，其實也用到了類似質因數分解，只是其實我們可以更好的利用到因數這一個特性。

我用一個比較小的例子來說明我的思想吧：
下文題到的因數列表的意思是，恰好能夠構成整數的因數的集合

有同學說我因數列表沒說明白，那我在這舉個例子，12 = 2 * 3 * 2,那么[2, 3, 2]就是他的因數列表

n = 1的時候，這個最大整數要可以被1整除就行，那么這個數就是1，因數列表是[1]

n = 2的時候，這個最大整數要可以被1, 2整除，那么這個數就是1 * 2 = 2,因數列表是[1, 2]

n = 3的時候，這個最大整數要可以被1, 2, 3整除，那么這個數就是1 * 2 * 3 = 6，因數列表是[1, 2, 3]

看到這里其實還看不出什么，但是接下來就是重頭戲了

n = 4的時候，這個最大整數要可以被1, 2, 3, 4整除，這時候我們發(fā)現(xiàn)，n = 3的時候求出來的6包含了因數[2, 3]，而2又恰好是4的因數，那么其實可以發(fā)現(xiàn)，這個新的最小整數只要在舊的最小整數6的基礎上增添一個新的因數，讓4也可以在最小整數的因數列表里面找到所有的因數，那么也就是，我們在原本的因數列表里加入一個新的因數4 / 2 = 2(4 / 2 中的 2 來自 6 的因數列表里的 2)，也就是新的因數列表是[1, 2, 3, 2]，此時的最小整數是1 * 2 * 3 * 2 = 12

看到這里，我相信大家已經可以明白我的思路了，解決問題的方法就是，求輸入為n的最小整數，也就是要在輸入為n-1的最小整數的因數列表里面找出n的因數，然后把最后沒有找出來的因數給加入到因數列表里面。

而尋找因數的過程可以歸結如下：

list // 因數列表， index // 因數列表下標索引，用于循環(huán)

k = n / list[index], 如果 k 是個整數，說明list[index]是n的一個因數，那么n = k，也就是說，找到了一個因數之后，我們下次要找因數的n就沒有那么大了，畢竟已經有一個因數了。

如果k不是一個整數，說明list[index]不是n的因數，不做任何處理

index++

好了，現(xiàn)在我們可以求出輸入為n的時候的因數列表了。

一個新的問題來了，計算機沒辦法表示出這個因數列表的乘積，我們要怎么求出它對987654321的余數呢。答案就是 ((a % c) * (b % c)) % c = (a * b) % c。在這個題里，也就是，我們不斷用result乘因數列表里的數的時候，我們就result = result % 987654321，可以在保持結果不變的情況下減少result的值，乘完因數列表里所有的數后的result就是結果

我一個切圖仔。。還是js寫得舒服一點，用其他語言實現(xiàn)的話，其實理解了我的解題思路應該不難。（by the way）動態(tài)數組是真的好用嘻嘻嘻。

 function solution (n) {
     const list = [] // 因數列表
     let result = 1 // 結果
     for (let i = 1; i <= n; i++) { // 依次在不同的n值時的list添加新的因數
         let newFactor = i // 這個新的因數初始為i

          // 在list中尋找i的因數,并且減小newFactor
         for(let j = list.length; j >= 0; j--) {
             if (newFactor === 1) {
                // 此時的i可以被list中若干個數相乘得到
                 break
             }
             let item = list[j]
             if (newFactor % item === 0) { // 如果這個數可以被list[j]整除
                 newFactor /= item // 縮小newFactor
             }
         }
         if (newFactor !== 1) { // 如果這個因數還有剩余部分
             list.push(newFactor) // 把剩余部分添加進list
 
             // 并且把因數乘入result
             result = (result * newFactor) % 987654321
         }
     }
    
    return result
 }

附上測試圖把：

那么這個算法題就到這了，如果大家又什么好的想法或者我的有什么問題，歡迎在討論區(qū)和我交流（雖然我知道你們都不想看這又臭又長的）

在評論區(qū)里，@JMC_給出了效率更高的解法，本來想補上他的思路的，發(fā)現(xiàn)我的文筆有限，說不清楚，大家可以看他的代碼JMC_的解法C++版

JMC_的原話是：

剛測試了一下你的代碼，發(fā)現(xiàn)你這個時間復雜度是O(n*n)。其實算1-n的最小公倍數的話，只要算1-n中的質數的貢獻就可以了，每個質數p的貢獻就是p的最大冪（小于等于n ），然后將所有的貢獻累乘起來就是答案了，這樣時間復雜度就會降成O(n)。

我用javascript重寫了一下，大家可以用node運行一下，然后自己模仿程序運行的過程應該就可以理解了。

function work (n) {
    const isprime = [] // 判斷一個數是否是質數
    const prime = [] // 質數列表
    let result = 1
    for (let i = 2; i <= n; i++) {// 一開始我們認為每一個數都可能是自身的冪
        isprime[i] = i
    }
    for (let i = 2; i <= n; i++) { //線性篩
        if (isprime[i] == i) { //i為質數
            prime.push(i)
            result = (result * i) % 987654321
        }
        for (let j = 0; i * prime[j] <= n; j++) { // 遍歷質數列表
            if (isprime[i] === prime[j]) { // i * prime[j]為質數的冪
                isprime[i*prime[j]] = prime[j]
                result = (result * prime[j]) % 987654321
            }
            else isprime[i * prime[j]] = 0
            if (i % prime[j] == 0) break
        }
        console.log(i)
        console.log("isprime")
        console.log(isprime)
        console.log("prime")
        console.log(prime)
        console.log("


")
    }
    return result
}