华为面试手撕真题【求1-n的最小公倍数】_输入一个n,求能整除1-n的最小正整数

输入一个n （1 <= n <= 10000)
求能整除1-n的最小正整数，即最小公倍数

数学要学好，互质的两个数的最小公倍数就是两个相乘，之后在考虑合数。

我们先使用筛法筛出质数，合数中又可以分为两类，一类是合数等于一个质数的k次方，也就是说他和其中一个质数的最小公倍数等于他本身，另一类则可以用质数和质数相乘表示，化简可以变成1。

举个例子，1-10的最小公倍数，lcm(1 2 3 4 5 6 7 8 9 10) 可以化为 lcm(1 1 1 1 5 1 7 8 9 1)相乘。

首先6是2和3的最小公倍数，所以2和3同时存在的时候，6就可以去掉，保留2和3即可。

10也同理，2和5就可以i表示10。

然后再来某个数字是某个素数的k次方的，当该数字存在时，他的那个素数因子就可以被去掉，例如4，8。因为8是2的3次方，4是2的2次方，当4存在的时候可以直接把2删去，当8存在的时候可以把4删去。

故而我们得到lcm[1,10]的最小公倍数为5*7*8*9 = 2520。

因此我们只需要用n以内所有质数的小于n的k次方那个数来替换质数即可。