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

凤舞凰扬

浏览: 66609 次
性别:
来自: 杭州

最近访客更多访客>>

san_yun

longx_ok

yang755994

fushuxiong

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

算法 Ruby Chrome Groovy Google

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

分享到：

欢迎大家加入这个圈子 | 如何设计电子商务产品表的物理模型

2009-10-26 11:14
浏览 4094
评论(22)
论坛回复 / 浏览 (22 / 10682)
分类:编程语言
查看更多

22 楼幸存者 2009-11-05

恩，看起来之前的方法还有问题。
其实可以分为奇偶两部分，偶数提取公因数2之后就成了连续整数，然后再分奇偶，依此类推。

21 楼凤舞凰扬 2009-11-05

感觉后面几个朋友又把简单问题复杂化了....

20 楼 night_stalker 2009-11-04

分组么，分一两次没什么效果的。想想就知道 gcd(a, a+1) 的辗转相除只用 1 步 ……

但是可以每步都分两组，二叉后变成只用求 log(m) 次 lcm。
最后就是（非常粗略的估算，用了很多约等于）
O((m/2) * log(n) + (m/4) * log(n^2) + (m/8) * log(n^4) + ... )
= O(m * log(m) * log(n) / 2)

require 'mathn'
range = 15..1000
puts range.inject(range.to_a){|acc, _|
  if acc.size == 1
    break acc[0]
  else
    acc.each_slice(2).map{|(a,b)| a.lcm(b || 1)}
  end
}

load 素数表要分配内存吧，内存比 CPU 慢很多。。。

19 楼幸存者 2009-11-04

楼上，分解质因数用不着穷举，还可以查素数表。

另外，连续两数的最小公倍数为两数之积
两数相差2，若是偶数，最小公倍数为两数之积除以2，若是奇数，最小公倍数为两数之积

连续m个数可以分为每4个一组
a, a+1, a+2, a+3
lcm(a,a+1) = a*(a+1);
lcm(a+2,a+3) ＝ (a+2)(a+3);
若a%2==0, lcm(a, a+2) = a*(a+2)/2, lcm(a+1,a+3) = (a+1)(a+3)
若a%2==1, lcm(a+1,a+3) = (a+1)(a+3)/2, lcm(a, a+2) = a*(a+2)
所以lcm(a,a+1,a+2,a+3) = a*(a+1)*(a+2)*(a+3)/2
然后各组lcm再求lcm，好歹比逐个累积好点。
当然，也许有更好的办法

18 楼 night_stalker 2009-11-04

讨论一下复杂度：
lcm (least common multiple) 的复杂度和 gcd (greatest commn denominator) 相同，因为
lcm(a,b) = a*b/gcd(a,b)

如果用 euclid 算法，对于大小为 n 的数字，lcm 的复杂度为
O(log(n) + log(n^2) + log(n^3) + ...) = O(m * m * log(n) / 2)
所以求 m 个连续自然数的最小公倍数（显然 m < n），代码的复杂度约为 O(m * log(n))。

分解质因数的方法 …… 穷举 n 以下的质数，就得 O(n * log(n)) 了吧……

edit: 改简单了点

17 楼 RednaxelaFX 2009-11-04

对还没升级到Ruby 1.9的人：

# 这是一个完整的程序：打印 5 到 500 这 496 个连续自然数的最小公倍数
require 'mathn'
puts (5..500).inject {|acc,e| acc.lcm e}

16 楼 night_stalker 2009-11-04

让大家看到 ruby 实在很不好意思，但我实在忍不住……

# 这是一个完整的程序：打印 5 到 500 这 496 个连续自然数的最小公倍数
require 'mathn'
puts (5..500).inject(&:lcm)

注1：不会溢出
注2：lcm == 最小公倍数

15 楼 potian 2009-11-04

SICP有比较详细的讲述

1.用费马测试的时间复杂度是O(logn)
2.可以fool费马测试的数字非常少：1亿以下的数字共为255个，你可以首先判断是不是在这255个中间
3.1亿以上数字中能够fool费马测试的概率大约等于宇宙射线导致计算机计算出错的概率
4.如果还不满意，可以用Miller-Rabin算法

14 楼凤舞凰扬 2009-11-04

lcllcl987 写道

我不知道算法。
java.math.BigInteger的isProbablePrime方法对于小范围类的素数求解基本够用。

这么多年，还从来没有用到过，呵呵，又学习了一把！

13 楼 lcllcl987 2009-11-04

我不知道算法。
java.math.BigInteger的isProbablePrime方法对于小范围类的素数求解基本够用。

12 楼 lcllcl987 2009-11-04

groovy脚本：
求1000内的素数：

primes=[]
(2g..1000g).each
{
if(it.isProbablePrime(100))
primes << it;
}

println "primes in 1000:" + primes

结果：
primes in 1000:
[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, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

11 楼 sunnycare 2009-11-03

“一段连续数中比较快捷地找到素数集合”
最快的算法就是埃拉脱色尼算法。
我举个例子，要求1-100间的质数表：那么先去掉2的倍数，剩下的数中比2大的最小数是3，再去掉3的倍数，剩下的数中比3大的最小数是5，再去掉5的倍数，以此类推。
google一下别人写的程序，自己实现的话，尽量用位运算，挺考验技巧的。
我建议你预先生成好素数表，不要每次都生成。

我觉得两个两个算最小公倍数，应该要比你用质数求快！！！！
因为，你用质数求，每个数都要算x遍除法。最后还要求x遍乘法。除法很占运算时间，比乘法还占。

两个两个算，只要一次除法，一次乘法，若干次移位运算。快速的多。
记[a,b]为a,b的最小公倍数，(a,b)是ab的最大公约数，那么[a,b]=ab/(a,b)
(a,b)的算法只要移位就可以算出。

这里还有个技巧：相邻的数是互质的，他们的最小公倍数就是他们的乘积。这样你可以把n个数的规模缩小到n/2的规模。

零零散散说几句，希望对你有帮助。

10 楼凤舞凰扬 2009-10-30

楼上，如果你都定义好素数集合了，也就不需要如此复杂的程序了，很简单就可以搞定的。
现在一个关键也就是如何在一段连续数中比较快捷地找到素数集合。

9 楼 qufulin 2009-10-27

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);
	}

}

8 楼 jxjjymx 2009-10-27

leeldy 写道

高等数学被我糟蹋了呢，现在后悔没有学好了。
我的程序是先将素数全部筛选出来，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。

elmar 写道

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

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

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

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

7 楼 leeldy 2009-10-26

6 楼 zhang_xzhi_xjtu 2009-10-26

凤舞凰扬写道

elmar 写道

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

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

凤舞凰扬写道

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

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

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

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

数学原理解释：
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的最大幂就是求该质数的幂指数了。

5 楼 leeldy 2009-10-26

凤舞凰扬写道

elmar 写道

leeldy 写道

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

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

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

4 楼 leeldy 2009-10-26

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

3 楼凤舞凰扬 2009-10-26

elmar 写道

leeldy 写道

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

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论