查找一系列数字的最小公倍数
https://stackoverflow.com/questions/185781
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我今天看了一篇有趣的DailyWTF帖子， <！> “出于所有可能的答案...... <！>”; 它让我感兴趣，可以挖掘原始的论坛帖子提交的地方。这让我想到如何解决这个有趣的问题 - 原始问题是在 3个或更多数字的最小公倍数但它的答案与我已经想出的相同的基本代码并没有真正的解释，所以我觉得这有点不同，可以保持开放。
解决方案
这个问题很有意思，因为它不需要你找到一组任意数字的LCM，你给了一个连续的范围。您可以使用 Sieve of Eratosthenes 的变体来找到答案。
def RangeLCM(first, last):
factors = range(first, last+1)
for i in range(0, len(factors)):
if factors[i] != 1:
n = first + i
for j in range(2*n, last+1, n):
factors[j-first] = factors[j-first] / factors[i]
return reduce(lambda a,b: a*b, factors, 1)
编辑：最近的一个upvote让我重新审视这个超过3年的答案。我的第一个观察是，今天我会用
enumerate来编写它。为了使其与Python 3兼容，需要进行一些小的更改。
第二个观察结果是该算法仅在范围的起点为2或更小时起作用，因为它不会试图筛选出范围起点以下的公因子。例如，RangeLCM（10,12）返回1320而不是正确的660。
第三个观察结果是，没有人试图将这个答案用于任何其他答案。我的直觉说，随着范围变大，这将改善蛮力LCM解决方案。测试证明我的直觉是正确的，至少这一次。
由于该算法不适用于任意范围，我重写它以假设范围从1开始。我在最后删除了对reduce的调用，因为它更容易计算结果因为因素是产生。我相信新版本的功能更正确，更容易理解。
def RangeLCM2(last):
factors = list(range(last+1))
result = 1
for n in range(last+1):
if factors[n] > 1:
result *= factors[n]
for j in range(2*n, last+1, n):
factors[j] //= factors[n]
return result
以下是 Joe Bebel 提出的原始和解决方案的时序比较，在我的名字中称为RangeEuclid测试
>>> t=timeit.timeit
>>> t('RangeLCM.RangeLCM(1, 20)', 'import RangeLCM')
17.999292996735676
>>> t('RangeLCM.RangeEuclid(1, 20)', 'import RangeLCM')
11.199833288867922
>>> t('RangeLCM.RangeLCM2(20)', 'import RangeLCM')
14.256165588084514
>>> t('RangeLCM.RangeLCM(1, 100)', 'import RangeLCM')
93.34979585394194
>>> t('RangeLCM.RangeEuclid(1, 100)', 'import RangeLCM')
109.25695507389901
>>> t('RangeLCM.RangeLCM2(100)', 'import RangeLCM')
66.09684505991709
对于问题中给出的1到20的范围，Euclid的算法击败了我的新旧答案。对于1到100的范围，您可以看到基于筛选的算法，尤其是优化版本。
其他提示
答案在保理或主要权力方面根本不需要任何花哨的步法，而且大多数情况下都不需要Eratosthenes的Sieve。
相反，您应该通过使用Euclid算法计算GCD来计算单对的LCM（它不需要分解，实际上要快得多）：
def lcm(a,b):
gcd, tmp = a,b
while tmp != 0:
gcd,tmp = tmp, gcd % tmp
return a*b/gcd
然后你可以找到使用上面的lcm（）函数减少数组的总LCM：
reduce(lcm, range(1,21))
只要范围是1到N，就可以快速解决这个问题。
关键的观察是，如果n（<！> lt; N）具有素数分解p_1^a_1 * p_2^a_2 * ... p_k * a_k，
那么它将为LCM贡献与p_1^a_1和p_2^a_2，... p_k^a_k完全相同的因子。并且这些功率中的每一个也在1到N范围内。因此，我们只需要考虑低于N的最高纯素数。
例如20岁我们有
2^4 = 16 < 20
3^2 = 9 < 20
5^1 = 5 < 20
7
11
13
17
19
将所有这些主要权力相乘，我们得到了
所需的结果2*2*2*2*3*3*5*7*11*13*17*19 = 232792560
所以在伪代码中：
def lcm_upto(N):
total = 1;
foreach p in primes_less_than(N):
x=1;
while x*p <= N:
x=x*p;
total = total * x
return total
现在你可以调整内部循环以稍微不同地工作以获得更快的速度，并且你可以预先计算primes_less_than(N)函数。
编辑：
由于最近的一次upvote我决定重新审视这个，看看与其他列出的算法的速度比较是如何进行的。
对于Joe Beibers和Mark Ransoms方法，针对范围1-160进行10k次迭代的时间如下：
乔斯：1.85s 标记：3.26s 我的：0.33s这是一个日志日志图，结果最多为300。
我的测试代码可以在这里找到：
import timeit
def RangeLCM2(last):
factors = range(last+1)
result = 1
for n in range(last+1):
if factors[n] > 1:
result *= factors[n]
for j in range(2*n, last+1, n):
factors[j] /= factors[n]
return result
def lcm(a,b):
gcd, tmp = a,b
while tmp != 0:
gcd,tmp = tmp, gcd % tmp
return a*b/gcd
def EuclidLCM(last):
return reduce(lcm,range(1,last+1))
primes = [
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 ]
def FastRangeLCM(last):
total = 1
for p in primes:
if p>last:
break
x = 1
while x*p <= last:
x = x * p
total = total * x
return total
print RangeLCM2(20)
print EculidLCM(20)
print FastRangeLCM(20)
print timeit.Timer( 'RangeLCM2(20)', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( 'EuclidLCM(20)', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( 'FastRangeLCM(20)', "from __main__ import FastRangeLCM" ).timeit(number=10000)
print timeit.Timer( 'RangeLCM2(40)', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( 'EuclidLCM(40)', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( 'FastRangeLCM(40)', "from __main__ import FastRangeLCM" ).timeit(number=10000)
print timeit.Timer( 'RangeLCM2(60)', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( 'EuclidLCM(60)', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( 'FastRangeLCM(60)', "from __main__ import FastRangeLCM" ).timeit(number=10000)
print timeit.Timer( 'RangeLCM2(80)', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( 'EuclidLCM(80)', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( 'FastRangeLCM(80)', "from __main__ import FastRangeLCM" ).timeit(number=10000)
print timeit.Timer( 'RangeLCM2(100)', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( 'EuclidLCM(100)', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( 'FastRangeLCM(100)', "from __main__ import FastRangeLCM" ).timeit(number=10000)
print timeit.Timer( 'RangeLCM2(120)', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( 'EuclidLCM(120)', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( 'FastRangeLCM(120)', "from __main__ import FastRangeLCM" ).timeit(number=10000)
print timeit.Timer( 'RangeLCM2(140)', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( 'EuclidLCM(140)', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( 'FastRangeLCM(140)', "from __main__ import FastRangeLCM" ).timeit(number=10000)
print timeit.Timer( 'RangeLCM2(160)', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( 'EuclidLCM(160)', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( 'FastRangeLCM(160)', "from __main__ import FastRangeLCM" ).timeit(number=10000)
哈斯克尔的单行。
wideLCM = foldl lcm 1
这就是我用于自己的Project Euler Problem 5。
在Haskell：
listLCM xs = foldr (lcm) 1 xs
您可以传递一个列表，例如：
*Main> listLCM [1..10]
2520
*Main> listLCM [1..2518]
266595767785593803705412270464676976610857635334657316692669925537787454299898002207461915073508683963382517039456477669596355816643394386272505301040799324518447104528530927421506143709593427822789725553843015805207718967822166927846212504932185912903133106741373264004097225277236671818323343067283663297403663465952182060840140577104161874701374415384744438137266768019899449317336711720217025025587401208623105738783129308128750455016347481252967252000274360749033444720740958140380022607152873903454009665680092965785710950056851148623283267844109400949097830399398928766093150813869944897207026562740359330773453263501671059198376156051049807365826551680239328345262351788257964260307551699951892369982392731547941790155541082267235224332660060039217194224518623199770191736740074323689475195782613618695976005218868557150389117325747888623795360149879033894667051583457539872594336939497053549704686823966843769912686273810907202177232140876251886218209049469761186661055766628477277347438364188994340512556761831159033404181677107900519850780882430019800537370374545134183233280000
一个或多个数字的最小公倍数是所有数字中所有不同素数因子的乘积，每个素数都取决于该素数出现在所述数字中的所有幂的最大值的幂。 LCM of。
假设900 = 2 ^ 3 * 3 ^ 2 * 5 ^ 2,26460 = 2 ^ 2 * 3 ^ 3 * 5 ^ 1 * 7 ^ 2。 2的最大功率为3,3的最大功率为3,5的最大功率为1,7的最大功率为2，任何更高的素数的最大功率为0。 所以LCM是：264600 = 2 ^ 3 * 3 ^ 3 * 5 ^ 2 * 7 ^ 2.
print "LCM of 4 and 5 = ".LCM(4,5)."\n";
sub LCM {
my ($a,$b) = @_;
my ($af,$bf) = (1,1); # The factors to apply to a & b
# Loop and increase until A times its factor equals B times its factor
while ($a*$af != $b*$bf) {
if ($a*$af>$b*$bf) {$bf++} else {$af++};
}
return $a*$af;
}
Haskell中的算法。这是我现在认为算法思维的语言。这可能看起来很奇怪，复杂，而且不受欢迎 - 欢迎来到Haskell！
primes :: (Integral a) => [a]
--implementation of primes is to be left for another day.
primeFactors :: (Integral a) => a -> [a]
primeFactors n = go n primes where
go n ps@(p : pt) =
if q < 1 then [] else
if r == 0 then p : go q ps else
go n pt
where (q, r) = quotRem n p
multiFactors :: (Integral a) => a -> [(a, Int)]
multiFactors n = [ (head xs, length xs) | xs <- group $ primeFactors $ n ]
multiProduct :: (Integral a) => [(a, Int)] -> a
multiProduct xs = product $ map (uncurry (^)) $ xs
mergeFactorsPairwise [] bs = bs
mergeFactorsPairwise as [] = as
mergeFactorsPairwise a@((an, am) : _) b@((bn, bm) : _) =
case compare an bn of
LT -> (head a) : mergeFactorsPairwise (tail a) b
GT -> (head b) : mergeFactorsPairwise a (tail b)
EQ -> (an, max am bm) : mergeFactorsPairwise (tail a) (tail b)
wideLCM :: (Integral a) => [a] -> a
wideLCM nums = multiProduct $ foldl mergeFactorsPairwise [] $ map multiFactors $ nums
这是我对它的Python抨击：
#!/usr/bin/env python
from operator import mul
def factor(n):
factors = {}
i = 2
while i <= n and n != 1:
while n % i == 0:
try:
factors[i] += 1
except KeyError:
factors[i] = 1
n = n / i
i += 1
return factors
base = {}
for i in range(2, 2000):
for f, n in factor(i).items():
try:
base[f] = max(base[f], n)
except KeyError:
base[f] = n
print reduce(mul, [f**n for f, n in base.items()], 1)
第一步获得数字的主要因素。第二步构建一个哈希表，其中列出了每个因子的最大次数，然后将它们相乘。
这可能是迄今为止我见过的最干净，最简短的答案（在代码行方面）。
def gcd(a,b): return b and gcd(b, a % b) or a
def lcm(a,b): return a * b / gcd(a,b)
n = 1
for i in xrange(1, 21):
n = lcm(n, i)
这是我在JavaScript中的答案。我首先从素数接近这个，并开发了一个很好的可重用代码函数来找到素数并找到素数因子，但最终决定这种方法更简单。
我的答案没有什么独特之处，上面没有发布，只是在Javascript中，我没有具体看到。
//least common multipe of a range of numbers
function smallestCommons(arr) {
arr = arr.sort();
var scm = 1;
for (var i = arr[0]; i<=arr[1]; i+=1) {
scm = scd(scm, i);
}
return scm;
}
//smallest common denominator of two numbers (scd)
function scd (a,b) {
return a*b/gcd(a,b);
}
//greatest common denominator of two numbers (gcd)
function gcd(a, b) {
if (b === 0) {
return a;
} else {
return gcd(b, a%b);
}
}
smallestCommons([1,20]);
这是我的javascript解决方案，希望您能轻松理解：
function smallestCommons(arr) {
var min = Math.min(arr[0], arr[1]);
var max = Math.max(arr[0], arr[1]);
var smallestCommon = min * max;
var doneCalc = 0;
while (doneCalc === 0) {
for (var i = min; i <= max; i++) {
if (smallestCommon % i !== 0) {
smallestCommon += max;
doneCalc = 0;
break;
}
else {
doneCalc = 1;
}
}
}
return smallestCommon;
}
以下是使用C Lang的解决方案
#include<stdio.h>
int main(){
int a,b,lcm=1,small,gcd=1,done=0,i,j,large=1,div=0;
printf("Enter range\n");
printf("From:");
scanf("%d",&a);
printf("To:");
scanf("%d",&b);
int n=b-a+1;
int num[30];
for(i=0;i<n;i++){
num[i]=a+i;
}
//Finds LCM
while(!done){
for(i=0;i<n;i++){
if(num[i]==1){
done=1;continue;
}
done=0;
break;
}
if(done){
continue;
}
done=0;
large=1;
for(i=0;i<n;i++){
if(num[i]>large){
large=num[i];
}
}
div=0;
for(i=2;i<=large;i++){
for(j=0;j<n;j++){
if(num[j]%i==0){
num[j]/=i;div=1;
}
continue;
}
if(div){
lcm*=i;div=0;break;
}
}
}
done=0;
//Finds GCD
while(!done){
small=num[0];
for(i=0;i<n;i++){
if(num[i]<small){
small=num[i];
}
}
div=0;
for(i=2;i<=small;i++){
for(j=0;j<n;j++){
if(num[j]%i==0){
div=1;continue;
}
div=0;break;
}
if(div){
for(j=0;j<n;j++){
num[j]/=i;
}
gcd*=i;div=0;break;
}
}
if(i==small+1){
done=1;
}
}
printf("LCM = %d\n",lcm);
printf("GCD = %d\n",gcd);
return 0;
}
在扩展@Alex的评论时，我会指出，如果你可以将数字计算到它们的素数，删除重复项，然后乘出，你就会有答案。
例如，1-5的素数因子为2,3,2,2,5。从'4'的因子列表中删除重复的'2'，你有2,2,3,5。将它们相乘得到60，这是你的答案。
上一条评论中提供的Wolfram链接 http://mathworld.wolfram.com/LeastCommonMultiple。 html 采用了更为正式的方法，但简短版本就在上面。
干杯。
不隶属于 StackOverflow
