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

      本来是有个问题，如何在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）。当然了，可以近似地完成后续（至少从界面上看不出太多差别）

我知道一个非常简单的加法方法求多个自然数的最小公倍数，只有加法和循环，循环次数过多，我怕随着数的增多，效率会越来越低。
不过用传统的辗转相除法，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

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

   楼上列出的这个算法不错,比我前面想出的更好，不过我还是没有理解每个素数不大于N的最大幂所包含的数学原理。

package com.acm;

import java.math.BigInteger;

public class CommonMutiple {

	//素数筛选表
	private boolean[] primes;
	//素数统计表
	private int[] count;
	
	public void cal(int[] numbers){
		int max=0;
		for(int i=0;i<numbers.length;i++){
			if(max<numbers[i]){
				max=numbers[i];
			}
		}
		//筛选指定范围内素数
		this.choicePrimes(max);
		
		//逐个数分解为素数，统计
		for(int i=0;i<numbers.length;i++){
			this.decompose(numbers[i]);
		}
		
		//获得最大公倍数
		BigInteger result=BigInteger.valueOf(2);
		BigInteger temp=null;
		result=result.pow(this.count[0]);
		for(int i=1;i<count.length;i++){
			if(this.count[i]==0){
				continue;
			}
			int j=i*2+1;
			temp=BigInteger.valueOf(j);
			result=result.multiply(temp.pow(this.count[i]));
		}
		
		System.out.println(result.toString());
	}
	
	//num被分解数，除数
	public void decompose(int num){
		
		int total=0;
		//分解2的个数
		while((num&1)==0){
			total++;
			num/=2;
		}
		if(this.count[0]<total){
			this.count[0]=total;
		}
		
		for(int i=1;i<primes.length;i++){
			if(this.primes[i]){
				continue;
			}
			int j=i*2+1;
			total=0;
			while(num%j==0){
				total++;
				num/=j;
			}
			if(this.count[i]<total){
				this.count[i]=total;
			}
		}
	}
	
	//筛选指定范围内的素数,false表示是素数
	public void choicePrimes(int max){
		int length=max/2+1;
		this.primes=new boolean[length];
		this.count=new int[length];
		//去掉1
		this.primes[0]=false;
		for(int i=1;i<length;i++){
			if(!this.primes[i]){
				int j=i*2+1;
				for(int k=j+j+j;k<max;k+=j+j){
					this.primes[(k-1)/2]=true;
				}
			}
		}
	}
	
	public static void main(String[] agrs){
		int[] nums={1000,1001,1002};
		CommonMutiple cm=new CommonMutiple();
		cm.cal(nums);
	}
}

无测试数据，不保证不会错，不保证无bug

我也不懂，就用不懂的方法作吧。

这个算法和楼上的简单的算法的思路是一样的，只不过计算的过程有了变化。


数学原理解释：
1 这里应用了算术基本定理。
   任何一个自然数N>1，都可以唯一的分解成质因数的连乘积，即
　　N=(P1^a1)*(P2^a2)......(Pn^an) (N>1)
  　其中P1，P2，P3，.......，Pn 为互不相等的质数且递增排列。
    a1，a2，......，an 为自然数。
2 最小公倍数
  整数m>1,n>1，如何求lcm(m,n)呢。
  1 把m,n展开为标准的质数连乘积形式。
  2 则lcm(m,n)的标准的质数连乘积形式中的质数必定来自于m或者n的标准的质数连乘积形式中的质数，其幂值为m,n中该质数对应的幂值的最大值。

  例子
  8=(2^3)
  12=(2^2)(3^1)
  lcm(m,n)=(2^3)(3^1)=24

  扩展一下，如何求N个数的lcm呢。
  1 把N个数展开为标准的质数连乘积形式。
  2 则lcm的标准的质数连乘积形式中的质数必定来自于这N个数的标准的质数连乘积形式中的质数，其幂值为在这N个数的标准的质数连乘积形式中该质数对应的幂值的最大值。
 
  例子
  12=(2^2)(3^1)
  10=(2^1)(5^1)
  8=(2^3)
  lcm=(2^3)(3^1)(5^1)=120

简单的总结一下这种算法的思路，就是确定lcm的质数因子和质数因子的幂指数。

对于leeldy的算法，其实和搂主的还是有一定区别的。
搂主的简单算法可以计算任意的连续整数的lcm。
而leeldy的算法只能计算从1开始的连续N个整数的lcm。

leeldy的算法中
因为是求1-N的连续的整数的lcm，所以1-N中的所有质数都在lcm的标准的质数连乘积中。
而求每个质数的不大于N的最大幂就是求该质数的幂指数了。

高等数学被我糟蹋了呢，现在后悔没有学好了。
我的程序是先将素数全部筛选出来，20w以内的应该都不要什么时间。
然后将那些连续的数分解质因数，统计单个质因数个数，最后将各个质因数的最大值得出，再用乘法算出来就可以了。
就像你的例子楼上的例子一样：
  例子
  12=(2^2)(3^1)
  10=(2^1)(5^1)
  8=(2^3)
  lcm=(2^3)(3^1)(5^1)=120

先将12以内的素数筛选出来，然后将8，10，12分解质因数，最后求出单个素数的最大数量(2-2,3-1,5-1)，然后相乘(2^2*3^1*5^1)=120。

这连个好像是一样的。
那求质数的要更直观一点
不知道效率如何。。。

package ccgc;
import java.math.BigInteger;  
public class CommonMutiple {

	/**
	 * @param args
	 */
	//定义素数常量数组
	private static int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 
                       31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
		     73, 79, 83, 89, 97, 101};
         //计算最小公倍数函数
	public static BigInteger calculationMutiple(int n){
		int[] array = new int[n];
		for(int i = 0; i < n; i++){
			array[i] = i + 1;
		}
		BigInteger temp = BigInteger.valueOf(1);
		int pos = 0;
		double js = Math.sqrt(n);
		while(true){
			boolean flag = false;
			int prime = primes[pos];
			for(int i = 0; i < n; i++){
				int j = array[i];
				if(j % prime == 0){
					array[i] = j / prime;
					flag = true;
				}
			}
			if(flag){
				temp = temp.multiply(BigInteger.valueOf(prime));
				continue;
			}
			pos ++;
			if(primes[pos] >= n){
				for(int i = 0; i < n; i++){
					temp = temp.multiply(BigInteger.valueOf(array[i]));
				}
				break;
			}
		}
		return temp;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BigInteger test = calculationMutiple(10);
		System.out.println(test);
	}

}