Hay una solución rápida a esto, siempre que el intervalo es de 1 a N.
La observación clave es que si n (< N) tiene factorización prima p_1^a_1 * p_2^a_2 * ... p_k * a_k, entonces contribuirá exactamente los mismos factores a la LCM como p_1^a_1 y p_2^a_2, ... p_k^a_k. Y cada uno de estos poderes también está en el rango de 1 a N. Así, sólo es necesario tener en cuenta los más altos poderes principales puros menor que N.
Por ejemplo, para 20 tenemos
2^4 = 16 < 20
3^2 = 9 < 20
5^1 = 5 < 20
7
11
13
17
19
Multiplicando todos estos poderes primos juntos obtenemos el resultado requerido de
2*2*2*2*3*3*5*7*11*13*17*19 = 232792560
Así
en pseudo código:
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
Ahora usted puede ajustar el bucle interior a wo rk ligeramente diferente para obtener más velocidad, y puede precalcular la función primes_less_than(N).
EDIT:
Debido a un upvote reciente que decretó la revisitar esto, para ver cómo fue la comparación con la velocidad de los otros algoritmos enumerados.
Timing para el rango de 1-160 con 10k iteraciones, contra métodos Joe Beibers y Mark rescates son los siguientes:
Joes: 1.85s Marcas: 3.26s mía: 0.33s
Aquí hay un registro -log gráfico con los resultados hasta 300.
Código para mi prueba se puede encontrar aquí:
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)
por cierto - es la respuesta 10581480? Creo que es la respuesta correcta para el problema en particular :) – warren
@warren - Me asusté por su respuesta, ya que por un tiempo pensé que tenía razón (solo encontré esta pregunta), y la calculadora de lcm que escribí en Haskell estaba dando una respuesta muy diferente, y 10581480 parecía ser divisible por [1..20]. Debo haber cometido un error en alguna parte, ya que su respuesta no es divisible por 11 o 16. La respuesta correcta es 232792560. –
@Matt Ellen - buena llamada, no estoy seguro de cómo me perdí 11 en mi respuesta :) – warren