Там очень быстрое решение для этого, до тех пор, диапазон составляет от 1 до N.
Ключевое наблюдение состоит в том, что если n (< N) имеет разложение на простые множители p_1^a_1 * p_2^a_2 * ... p_k * a_k, то это будет способствовать те же факторы, МДК, как 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
Теперь вы можете настроить внутреннюю петлю на горе rk несколько иначе, чтобы получить большую скорость, и вы можете предварительно вычислить функцию primes_less_than(N).
EDIT:
В связи с недавним upvote я decideded, чтобы вернуться к этому, чтобы увидеть, как сравнение скорости с другими перечисленными алгоритмами пошли.
Timing для диапазона 1-160 с 10к итераций, против Джо Beibers и Марк выкупы методы заключаются в следующем:
Джос: 1.85s Marks: 3.26s Mine: 0.33s
Вот журнал -log график с результатами до 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)
кстати - это ответ 10581480? Я считаю, что это правильный ответ для конкретной проблемы :) – warren 2009-02-12 19:12:03
@warren - Я был взволнован вашим ответом, так как какое-то время я думал, что вы правы (только что нашел этот вопрос), и калькулятор lcm, который я написал в Хаскелл дал совершенно другой ответ, и 10581480, казалось, был делимым на [1..20]. Я, должно быть, допустил ошибку где-то, так как ваш ответ неравно делится на 11 или 16. Правильный ответ 232792560. – 2010-01-28 10:17:56
@Matt Ellen - хороший звонок, не уверенный, как я пропустил 11 в своем ответе :) – warren 2010-01-28 14:27:33