Menu Close

Menor divisible por todos

José A. Alonso,

Definir la función

   menorDivisible :: Integer -> Integer -> Integer

tal que (menorDivisible a b) es el menor número divisible por todos los números desde a hasta b, ambos inclusive. Por ejemplo,

   menorDivisible 1 10                        ==  2520
   length (show (menorDivisible 1 (3*10^5)))  ==  130141

Nota: Este ejercicio está basado en el problema 5 del Proyecto Euler

Soluciones

import Data.List (foldl')
 
-- 1ª solución
-- ===========
 
menorDivisible :: Integer -> Integer -> Integer
menorDivisible a b =
  head [x | x <- [b..]
          , and [x `mod` y == 0 | y <- [a..b]]]
 
-- 2ª solución
-- ===========
 
menorDivisible2 :: Integer -> Integer -> Integer
menorDivisible2 a b  
  | a == b    = a
  | otherwise = lcm a (menorDivisible (a+1) b)
 
-- 3ª solución
-- ============
 
menorDivisible3 :: Integer -> Integer -> Integer
menorDivisible3 a b = foldl lcm 1 [a..b] 
 
-- 4ª solución
-- ===========
 
menorDivisible4 :: Integer -> Integer -> Integer
menorDivisible4 a b = foldl1 lcm [a..b] 
 
-- 5ª solución
-- ===========
 
menorDivisible5 :: Integer -> Integer -> Integer
menorDivisible5 a b = foldl' lcm 1 [a..b] 
 
-- 6ª solución
-- ===========
 
menorDivisible6 :: Integer -> Integer -> Integer
menorDivisible6 a b = foldr1 lcm [a..b] 
 
-- 7ª solución
-- ===========
 
menorDivisible7 :: Integer -> Integer -> Integer
menorDivisible7 a = foldr1 lcm . enumFromTo a
 
-- Comparación de eficiencia
-- =========================
 
--   λ> menorDivisible 1 17
--   12252240
--   (18.63 secs, 15,789,475,488 bytes)
--   λ> menorDivisible2 1 17
--   12252240
--   (13.29 secs, 11,868,764,272 bytes)
--   λ> menorDivisible3 1 17
--   12252240
--   (0.00 secs, 114,688 bytes)
--   λ> menorDivisible4 1 17
--   12252240
--   (0.01 secs, 114,752 bytes)
--   λ> menorDivisible5 1 17
--   12252240
--   (0.01 secs, 110,640 bytes)
--   λ> menorDivisible6 1 17
--   12252240
--   (0.01 secs, 114,752 bytes)
--   λ> menorDivisible7 1 17
--   12252240
--   (0.00 secs, 110,912 bytes)
--   
--   λ> length (show (menorDivisible3 1 (10^5)))
--   43452
--   (1.54 secs, 2,021,887,000 bytes)
--   λ> length (show (menorDivisible4 1 (10^5)))
--   43452
--   (1.47 secs, 2,021,886,616 bytes)
--   λ> length (show (menorDivisible5 1 (10^5)))
--   43452
--   (0.65 secs, 2,009,595,568 bytes)
--   λ> length (show (menorDivisible6 1 (10^5)))
--   43452
--   (0.30 secs, 172,986,840 bytes)
--   λ> length (show (menorDivisible7 1 (10^5)))
--   43452
--   (0.30 secs, 172,986,920 bytes)
--   
--   λ> length (show (menorDivisible5 1 (2*10^5)))
--   86871
--   (2.47 secs, 7,989,147,304 bytes)
--   λ> length (show (menorDivisible6 1 (2*10^5)))
--   86871
--   (0.89 secs, 533,876,496 bytes)
--   λ> length (show (menorDivisible7 1 (2*10^5)))
--   86871
--   (0.88 secs, 533,875,608 bytes)

Pensamiento

Será el peor de los malos
bribón que olvide
su vocación de diablo.

Antonio Machado

Posted in Medio
Tagged , , , , , , , , , , ,

4 Comments

  1. ignarrrod
    Responder 
    menorDivisible :: [Integer] -> Integer
menorDivisible []       = 1
menorDivisible [x]      = x
menorDivisible (x:y:xs) = lcm (lcm x y) (menorDivisible xs)
  2. rocsantru
    Responder 
    menorDivisible :: Integer -> Integer -> Integer
menorDivisible a b = foldr1 lcm [a..b] 
 
-- λ> length (show (menorDivisible 1 (3*10^5)))
-- 130141
-- (1.55 secs, 1,071,519,504 bytes)
  3. rocsantru
    Responder

    En Python

    from functools import reduce
from numpy import lcm
 
 
def menorDivisible(a, b):
    return reduce(lcm, range(a, b + 1))
 
 
# Sólo sirve para enteros pequeños. Por ejemplo,
#    >>> menorDivisible(1, 55)
#    2490225029858120672
#    >>> menorDivisible(1, 56)
#    -1015168864702706912
# La segunda respuesta no es correcta.
    • rocsantru
      Responder

      La siguiente funciona para números grandes

      from functools import reduce
from math import gcd
 
def mcm(x,y):
    return x*y//gcd(x,y)
 
def menorDivisible2(a, b):
    return reduce(mcm, range(a, b + 1))

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.