求一段连续自然数的最小公倍数

      本来是有个问题，如何在HTML中只使用一个table(也就是不能嵌套table,不使用div)的情况下，一个table有N行，每行的列数与对应的行的位置是相同的（也就是1行有1列，第2行有两列，依次类推，第N行有N列），要求每行中的每列都平均分割显示。

      当时一下子没有想起来，以为通过colspan加width可以实现，后来发现不对。只好用一个相对愚蠢的方式，也就是算出1到N之间的最小公倍数，然后对于每行，在除以行数，就得出colspan的值，从而实现这个问题。比如说有6行，它们的最小公倍数是2*5*6也就是60，那么第1行就是colspan=60, 第2行就是colspan=30, 第3行就是colspan=20，第4行就是colspan=15, 第5行就是colspan=12, 第6行就是colspan=10. 这样也就可以实现上述问题，当然了，这种方法是在N不会太大的情况下，否则最小公倍数是会溢出的。

      不过这个问题给我另外一个思考，如果N未定，但有限（比如不会溢出），那么如何比较快速有效地找到一系列连续自然数的最小公倍数？这种高效，本人希望是不仅对计算机而言，更对人而言。比如说通过数相乘然后除以下一个自然数，模数为0的忽略，不为0的再累积乘的方式，对计算机而言是快速的，但是对人而言就是复杂的了（每次计算一个大数除以一个较小数都比较麻烦）。

      虽然想到下面这个简单的算法，个人认为不算那么高效（因为需要对合数进行分解）。

      1. 对于每个数，如果是素数，则一定是最小公倍数的构成，参与计算。如果是合数，则分解成一组素数。

      2. 对于每个素数，都有一个类似map的结构（这种结构不仅仅是指语言的中map，而是类似的二维表），key为素数，value为素数出现的次数（可以是出现在自然数列中的，也可以是由合数分解出来的）。

      3. 如果合数分解出的素数组存在于map中（key=素数，value>=分解的素数次数），则该合数不参与计算中。

 

      呵呵，有兴趣的朋友可以讨论讨论，提提自己的想法。

 

 

----2009-10-27补充----

    昨天吃完饭散步的时候，突然把三楼elmar的数学原理想通了，其实一点都不难。我们知道任何合数都可以分解成两个或以上素数，因为合数本身是需要在连续数列范围中，那么分解出来的素数的乘积自然也必小于连续数列的最大边界数，又可以知道，由最小素数的幂次方肯定是最小值（也就是a<b<c, abc均为自然数, a*a*a<a*b*c），所以也就有了三楼列出的算法了。

   简单表述下，就是：

  1. 找出一段连续自然数列中的所有素数。

  2. 循环这个有序的素数数组，计算每个素数不大于自然数列中最大值的幂，然后累积相乘（这里有个优化，当某个下标的素数的平方已经开始大于最大值时，改下标及其后续素数均不需要在进行重复检查计算）

  顺便回到这个题目的最初原因，去构造这样一个表格，如果准确的话，其实这个N是必须小于9的，也就是最多是8，如果N为9，其最小公倍数将超过1000（9和10，均为2520），这样的colspan大部分浏览器不识别（包括IE, FIREFOX, google chrome）。当然了，可以近似地完成后续（至少从界面上看不出太多差别）

评论

2 楼 elmar 2009-10-26  

leeldy 写道

我知道一个非常简单的加法方法求多个自然数的最小公倍数，只有加法和循环，循环次数过多，我怕随着数的增多，效率会越来越低。
不过用传统的辗转相除法，N的数要做N-1辗转相处，效率也无法保证。

准备1-N之间的质数的集合
然后求每个质数的不大于N的最大幂，比如N=30时，2对应的最大幂是4。
然后最小公倍数就是所有质数的相应幂的积

比如N=10
小于10的质数有2,3,5,7
对应的最大幂是：3，2，1，1
则最小公倍数是：2^3x3^2x5^1x7^1 = 2520

不过这样做估计会很吃内存的

1 楼 leeldy 2009-10-26  

我知道一个非常简单的加法方法求多个自然数的最小公倍数，只有加法和循环，循环次数过多，我怕随着数的增多，效率会越来越低。
不过用传统的辗转相除法，N的数要做N-1辗转相处，效率也无法保证。