Inicialmente no estaba planeando escribir una respuesta. Pero me dijeron que después de que otro usuario hiciera la extraña afirmación de que simplemente multiplicar los primeros primos era más costoso desde el punto de vista computacional que aplicarlo repetidamente lcm. Así que aquí están los dos algoritmos y algunos puntos de referencia:
Mi algoritmo:
Algoritmo de primera generación, dándome una lista infinita de primos.
isPrime :: Int -> Bool
isPrime 1 = False
isPrime n = all ((/= 0) . mod n) (takeWhile ((<= n) . (^ 2)) primes)
toPrime :: Int -> Int
toPrime n
| isPrime n = n
| otherwise = toPrime (n + 1)
primes :: [Int]
primes = 2 : map (toPrime . (+ 1)) primes
Ahora usando esa lista principal para calcular el resultado para algunos N:
solvePrime :: Integer -> Integer
solvePrime n = foldl' (*) 1 $ takeWhile (<= n) (fromIntegral <$> primes)
Ahora, el otro algoritmo basado en mcm, que ciertamente es bastante conciso, principalmente porque implementé la primera generación desde cero (y no utilicé el algoritmo de comprensión de listas súper concisas debido a su bajo rendimiento), mientras que lcmsimplemente se importó del Prelude.
solveLcm :: Integer -> Integer
solveLcm n = foldl' (flip lcm) 1 [2 .. n]
-- Much slower without `flip` on `lcm`
Ahora para los puntos de referencia, el código que usé para cada uno era simple: ( -prof -fprof-auto -O2entonces +RTS -p)
main :: IO ()
main = print $ solvePrime n
-- OR
main = print $ solveLcm n
Para n = 100,000, solvePrime:
total time = 0.04 secs
total alloc = 108,327,328 bytes
vs solveLcm:
total time = 0.12 secs
total alloc = 117,842,152 bytes
Para n = 1,000,000, solvePrime:
total time = 1.21 secs
total alloc = 8,846,768,456 bytes
vs solveLcm:
total time = 9.10 secs
total alloc = 8,963,508,416 bytes
Para n = 3,000,000, solvePrime:
total time = 8.99 secs
total alloc = 74,790,070,088 bytes
vs solveLcm:
total time = 86.42 secs
total alloc = 75,145,302,416 bytes
Creo que los resultados hablan por sí mismos.
El generador de perfiles indica que la generación principal ocupa un porcentaje cada vez menor del tiempo de ejecución a medida que naumenta. Por lo tanto, no es el cuello de botella, por lo que podemos ignorarlo por ahora.
Esto significa que realmente estamos comparando llamadas lcmdonde un argumento va de 1 a n, y el otro va geométricamente de 1 a ans. Para llamar *con la misma situación y el beneficio adicional de omitir todos los números no primos (asintóticamente de forma gratuita, debido a la naturaleza más cara de *).
Y es bien sabido que *es más rápido que lcm, ya que lcmrequiere aplicaciones repetidas de mod, y modes asintóticamente más lento ( O(n^2)vs ~O(n^1.5)).
Entonces, los resultados anteriores y el breve análisis del algoritmo deberían hacer muy obvio qué algoritmo es más rápido.
