#JL-04 Lcm题解
原题：
Lcm
描述

现在你有一个正整数N。 你需要找到最小的正整数M使得M > N且lcm(N + 1,N + 2,…,M) = lcm(1,2,…,M)。

输入
输入一行一个正整数N

N ≤ 1000000

输出
输出一行一个正整数M。

输入样例 1

4
输出样例 1

8

##题解：
题意基础
LCM是Least Common Multiple 的缩写,表示最小公倍数。

核心 数论 素数线性筛

数学基础
初等数学基本定理：任一大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的。

思路
最小的正整数M满足M > N且lcm(N + 1,N + 2,…,M) = lcm(1,2,…,M)，观察发现左式被包含在右式之中，即lcm(1,2,…,N)=k·lcm(N + 1,N + 2,…,M)（k为≥2的正整数）。
结合初等数学基本定理，记录[1,N]中质数的最高阶次中最大的数（设其为X)。
欲使M满足要求，令M=2*X。
接下来只求[1,N]中质数的最高阶次中最大的数。

核心代码：

for(int i = 2; i <= n; i++)
    {
        if(!prime[i])//若为素数
        {
            int sum = i;
            while(sum <= n/i) sum *= i;
            m = max(m,(2*sum);
        }
    }

AC代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

int prime[1000010];

//素数线性筛 素数标记为0 约数标记为1
void Prime(){
    memset(prime, 0, sizeof(prime));
    prime[0] = prime[1] = 1;
    for (int i = 2; i * i <= 1000000; i++) {
        if (!prime[i]) {
            for (int j = i * i; j <= 1000000; j += i) {
                prime[j] = 1;
            }
        }
    }
}

int main(){
    Prime();
    long long n；
    cin>>n;
    long long m = 2;
    for(int i = 2; i <= n; i++)
    {
        if(!prime[i])//若为素数
        {
            int sum = i;
            while(sum <= n/i) sum *= i;
            m = max(m,(2*sum);
        }
    }
    cout<<m<<endl;
    return 0;
}