欧拉项目005:最小公倍数

参考文章：http://files.cnblogs.com/skyivben/005_overview.pdf。

最简单的就是从1，20两两求最小公倍数。

这里有一个公式：

lcm(1...n) == lcm([n/2]+1,n),[]是向上取整

我自己举了好多例子，在［n/2]+1...n之间的数，总能用（1...[n/2]）里的数相乘得到，所以lcm(1...n)==lcm([n/2]+1,n)

说是：对于 1 至  之间的每个数 a，在  至 n 之间刚好可以找到一个数 b，使得 2ka = b 。

我的python代码如下：

#lcm(1...n) == lcm([n/2]+1...n)
def gcd(a,b):
    #a>b
    while b:
        r = a % b
        a = b
        b = r
    return a
def lcm(a,b):
    return a/gcd(a,b)*b
N = 20
x = N/2+1
for y in range(N/2+2,N+1):
    x = lcm(x,y)
print x