Pro5:求前k个数的最小公倍数

Description：

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

solutions:

      这里不妨就k=20来分析，设N为最后要求的答案，则N必然可以写为p[1]^a[1]*p[2]^a[2]...,其中p[i]为小于k的素数，p[i]的求法用素数筛法即可，关键是求a[i].

     一种比较繁琐的方法是遍历小于k的数，求出这种表达形式后对每个素数的指数取最大值即可。

     令外一种方法是由于前k个数是连续的，故必然存在一个a[i]，对于任何大于a[i]的数x必有p[i]^x>k;所以有a[i]=(floor)log(k)/log(p[i]),进一步的优化得：对于大于limit(limit=sqrt(k))的素数来说，其a[i]必然为1.

详细介绍见官方的pdf文档：

文件:	005_overview.pdf
大小:	17KB
下载:	下载

由此问题我想到求任意k个连续的数的最小公倍数：

这个好像只能用第一种方法了，不知道还有没有更好的方法？