求1~N的最小公倍数

基本思路：

其实这个题目跟求1~100的质数（有人需要的话我会写这个程序）有异曲同工之妙，抓住特点：

a、从1开始的一个连续正整数序列

b、跟倍数有关

这样的题目可以用两个for语句（只要符合上面的特点，基本上都可以用这种思维方式）嵌套解决

这个题目计算过程说起来麻烦，我就举个例子来，你们一看就懂，而且写成程序也很好实现

比如1~12的最小公倍数

第一步：把这N个数放进一个数组（c，c++等语言）或者列表（python），比如Nlist =[1,2,3,4,5,6,7,8,9,10,11,12]

第二步：之后对这个列表的所有元素分别整除第一个不为1的数，如果不能整除的，就留下来，很难理解，那就看下面

Nlist =

第一次循环：

整除1（为了保持程序的美观，我把这次算进去了，第一次循环在实际操作中可以省略，因为1~N的最小公倍数，其实就是2~N的最小公倍数）：

[1,2,3,4,5,6,7,8,9,10,11,12]

同时，累乘器乘以1

第二次循环：

整除2（第一个不为1的数）：

[1,1,3,2,5,3,7,4,9,5,11,6]

累乘器乘以2

第三次循环：

整除3：

[1,1,1,2,5,1,7,4,3,5,11,2]

累乘器乘以3

上面看起来没有什么明显作用，但从这里开始有不同：

第四次循环：

整除2（因为第一个不为1的数字是2了）：

[1,1,1,1,5,1,7,2,3,5,11,1]

累乘器乘以2

第五次循环：

整除5（废话）：

[1,1,1,1,1,1,7,2,3,1,11,1]

依此类推，所以s = 1*2*3*2*5*7*2*3*11=27720跟实际情况相符

另外，还有三点可以值得发掘的：

1、通过以上的分析，可以知道，其实每次累乘器乘以的数不就是质数么？当然不包括第一次循环，因为其实第一次循环可以忽略的，只是为了更好符合接下来循环的规律才写上的，所以，问：1~N的质数？

2、我们知道，求两个数的最小公倍数怎么也不会想到我那种思维上面去，真的要求两个数的最小公倍数，用递归其实是最快的（这个以后写），或者说，根据最小公倍数的定义（百科）写才是对的，这个程序是因为题目要求具有那两个特点，所以可以这么做

3、如果说，这样的程序是特例，不是适用所有情况，而要是适用所有情况的话，可能程序比较复杂，那么就把这两者结合起来吧

还记得怎么求最大公约数吧？（不是说最小公倍数么？怎么又是最大公约数了，焚蛋！）不记得？嗯……我先假定你知道吧

假设求最大公约数的函数是Gys(num1,num2)，最小公倍数其实和最大公约数是有关系的，数学好的话知道，其实：最大公约数X最小公倍数=两者之积。靠，原来如此！难怪你要说最大公约数，其实不是，我说这个的目的是，如果你有写过最大公约数的程序，现在又要写最小公倍数，那为什么不借助已经有的程序来写现在的呢？这个想法就是函数的精髓啊！那有人说，我数学不好，那就看下面另一种方法：

通过这个程序的分析知道，其实最小公倍数跟质数是很有关系的，毕竟，你累乘器乘的都是质数，所以，尝试一下以下的步骤：

a、i从1开始到N结束，做这些事：

b、求前两个数x,y的最大公约数r，累乘器s=r* (x/r)*(y/r)，其中，如果你是从1开始循环的话，算下来之后x/r和y/r其实一定是两个质数！得到的结果s作为新的x和下一个数继续做这个步骤，也就是说x已经包含了累乘的结果。也就是说，要得到两个数的最小公倍数，其实就是最大公约数再乘以某个质数，有人反驳说2和1024的最小公倍数就不等于最大公约数2和一个质数的乘积，但注意我这里有个前提，就是是从1开始循环的，也就是说，应该要认为，2~1024的最小公倍数，那么应该认作是“2~1023的最小公倍数”和“1024”的最小公倍数才是“2~1023的最小公倍数”再和“1024”的最大公约数再乘以一个质数

很绕？那就不管，看下面过程

红字是x，蓝字是s，黄字是y，淡蓝字是r

比如

i=1时，计算1和2，s=1*(1/1)*(2/1)=2

i=2时，计算2和3，s=1*(2/1)*(3/1)=6

i=3时，计算6和4，s=2*(6/2)*(4/2)=12

i=4时，计算12和5，s=1*(12/1)*(5/1)=12

依次类推

细心的会发现s=r* (x/r)*(y/r)=x*y/r，这不就是一开始说的数学表达式么？即：最大公约数X最小公倍数=两者之积

没错，这个表达式是没错的，而之前说过了，x其实每次是会被更新的，被上一次得到的s替换掉，所以，累乘的步骤就隐藏在这里了