首页 > 代码库 > 欧拉项目005:最小公倍数

欧拉项目005:最小公倍数

Smallest multiple

Problem 5

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 positive number that is evenly divisible by all of the numbers from 1 to 20?

就是找出1....20 所有数的最小公倍数。

参考文章: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 至 n_2 之间的每个数 a,在 n_2_1 至 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