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

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

“一段连续数中比较快捷地找到素数集合”
最快的算法就是埃拉脱色尼算法。
我举个例子，要求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的规模。

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

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]

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

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

SICP有比较详细的讲述

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

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

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

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

对还没升级到Ruby 1.9的人：

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

讨论一下复杂度：
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: 改简单了点

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

另外，连续两数的最小公倍数为两数之积
两数相差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，好歹比逐个累积好点。
当然，也许有更好的办法