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

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

input: n
output: 一個(gè)可以被1到n的所有整數(shù)整除的最小整數(shù),
        由于整數(shù)過大，輸出這個(gè)整數(shù)對(duì)987654321取余的結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

而尋找因數(shù)的過程可以歸結(jié)如下：

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

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

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

index++

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

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

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

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

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

附上測(cè)試圖把：

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

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

JMC_的原話是：

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

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

function work (n) {
    const isprime = [] // 判斷一個(gè)數(shù)是否是質(zhì)數(shù)
    const prime = [] // 質(zhì)數(shù)列表
    let result = 1
    for (let i = 2; i <= n; i++) {// 一開始我們認(rèn)為每一個(gè)數(shù)都可能是自身的冪
        isprime[i] = i
    }
    for (let i = 2; i <= n; i++) { //線性篩
        if (isprime[i] == i) { //i為質(zhì)數(shù)
            prime.push(i)
            result = (result * i) % 987654321
        }
        for (let j = 0; i * prime[j] <= n; j++) { // 遍歷質(zhì)數(shù)列表
            if (isprime[i] === prime[j]) { // i * prime[j]為質(zhì)數(shù)的冪
                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
}