算法之不定期更新（一）（2018-04-12）

摘要：算法的确有他独特的魅力。然后我在做这个题的时候，其实也用到了类似质因数分解，只是其实我们可以更好的利用到因数这一个特性。判断一个数是否是质数质数列表一开始我们认为每一个数都可能是自身的幂线性筛为质数遍历质数列表为质数的幂

从三月份到现在，大大小小笔试了十几家公司（主要是因为一直solo code，没人内推），然后也能感觉到自己的进步把。从编程题只能ac一题到后来的ak。今天面腾讯的时候，面试官还一度怀疑我专门去刷了腾讯的笔试题。因此，我想开始做算法，也就是大家都知道的leetcode啦。其实真的蛮有意思的，建议前途未卜的在校大学生都可以去试一下。。算法的确有他独特的魅力。这个专栏我打算加进一块是，把我见到的有意思的算法题给拿出来，跟大家分享交流。

input: n
output: 一个可以被1到n的所有整数整除的最小整数,
        由于整数过大，输出这个整数对987654321取余的结果

这里给同学提个醒。。再往下直接就是我写得解题思路了，希望大家可以先自己思考一下这个问题。

我这里先给出一个，我跟别人交流之后，感觉是可以继续发展的想法：

先求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整除，这时候我们发现，n = 3的时候求出来的6包含了因数[2, 3]，而2又恰好是4的因数，那么其实可以发现，这个新的最小整数只要在旧的最小整数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 // 因数列表下标索引，用于循环

k = n / list[index], 如果 k 是个整数，说明list[index]是n的一个因数，那么n = k，也就是说，找到了一个因数之后，我们下次要找因数的n就没有那么大了，毕竟已经有一个因数了。

如果k不是一个整数，说明list[index]不是n的因数，不做任何处理

index++

好了，现在我们可以求出输入为n的时候的因数列表了。

一个新的问题来了，计算机没办法表示出这个因数列表的乘积，我们要怎么求出它对987654321的余数呢。答案就是 ((a % c) * (b % c)) % c = (a * b) % c。在这个题里，也就是，我们不断用result乘因数列表里的数的时候，我们就result = result % 987654321，可以在保持结果不变的情况下减少result的值，乘完因数列表里所有的数后的result就是结果

我一个切图仔。。还是js写得舒服一点，用其他语言实现的话，其实理解了我的解题思路应该不难。（by the way）动态数组是真的好用嘻嘻嘻。

 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
 }

附上测试图把：

那么这个算法题就到这了，如果大家又什么好的想法或者我的有什么问题，欢迎在讨论区和我交流（虽然我知道你们都不想看这又臭又长的）

在评论区里，@JMC_给出了效率更高的解法，本来想补上他的思路的，发现我的文笔有限，说不清楚，大家可以看他的代码JMC_的解法C++版

JMC_的原话是：

刚测试了一下你的代码，发现你这个时间复杂度是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
}