首页 > 代码库 > 欧拉项目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 至 之间的每个数 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。