#腾讯#2019秋招9月16日技术岗笔试第一题：最小公倍数

2018年9月16号上午10点的腾讯笔试，20道不定项，3道编程题。主要第一道当时没想出来。。。后面两道都比较简单，就讨论下第一道。

题目是，给定一个数n， 求另一个数m（m>n)，使得区间 [1, m] 内所有数的最小公倍数等于 [n+1, m] 的最小公倍数。

我的思路是;
假设函数f(n)=m，则:

1. f(n) ≥ f(n-1);

2. 如果n这数的质因数只有一个（除了1），则 f(n) = 2 * n;

3. 如果质因数个数不只一个，则 f(n) = f(n-1);

所以代码如下，不知道对不对，如果有AC的，麻烦回复下对错。

#include <iostream>

using namespace std;

int LeastCommonMultiple(int x) {
    if (x == 1) return 2;
    int temp = x;

	bool flag = false;  //初始假定质因数不只一个
    for (int i = 2; i <= temp; ++i) {
        if (temp % i == 0) { 
            do {
                temp /= i;
            }while(temp % i == 0);



	if (temp == 1) { //说明x = i的整数次幂
                flag = true;
            }
            break;
        }
    }

    if (flag) {
        return x << 1;
    }
    //如果x的质因数不止一个，则等于前一个数

return LeastCommonMultiple(x - 1);
}

int main() {
    int n;
    cin >> n;

    cout << LeastCommonMultiple(n) << endl;

    return 0;
}