Menu Close

Mayor divisor primo

Los divisores primos de 13195 son 5, 7, 13 y 29. Por tanto, el mayor divisor primo de 13195 es 29.

Definir la función

   mayorDivisorPrimo :: Integer -> Integer

tal que (mayorDivisorPrimo n) es el mayor divisor primo de n. Por ejemplo,

   mayorDivisorPrimo 13195            ==  29
   mayorDivisorPrimo 152416333181401  ==  12345701

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

Soluciones

import Data.Numbers.Primes (primeFactors)
 
-- 1ª solución  (sin librerías auxiliares)
-- =======================================
 
mayorDivisorPrimo :: Integer -> Integer
mayorDivisorPrimo = last . divisoresPrimos 
 
-- (divisoresPrimos n) es la lista de los divisores primos de n. Por
-- ejemplo, 
--    divisoresPrimos 13195  ==  [5,7,13,29]
divisoresPrimos :: Integer -> [Integer]
divisoresPrimos 0 = []
divisoresPrimos 1 = []
divisoresPrimos n = m : divisoresPrimos (n `div` m)
  where m = menorDivisorPrimo n 
 
-- (menorDivisorPrimo n) es el menor divisor primo de n. Por ejemplo, 
--    menorDivisorPrimo 24  ==  2
--    menorDivisorPrimo 25  ==  5
--    menorDivisorPrimo 29  ==  29
menorDivisorPrimo :: Integer -> Integer
menorDivisorPrimo x =
  head [y | y <- 2 : [3,5..(ceiling . sqrt . fromIntegral) x] ++ [x]
          , x `mod` y == 0]
 
-- 2ª solución (con la librería Data.Numbers.Primes)
-- =================================================
 
mayorDivisorPrimo2 :: Integer -> Integer
mayorDivisorPrimo2 = last . primeFactors
 
-- Comparación de eficiencia
-- =========================
 
--   λ> mayorDivisorPrimo 152416333181401
--   12345701
--   (1.96 secs, 1,630,201,856 bytes)
--   λ> mayorDivisorPrimo2 152416333181401
--   12345701
--   (2.01 secs, 5,445,284,432 bytes)

Pensamiento

“Un programa de ordenador es una demostración.” ~ Igor Rivin

6 soluciones de “Mayor divisor primo

  1. claniecas
    import Data.Numbers.Primes
     
    mayorDivisorPrimo :: Integer -> Integer
    mayorDivisorPrimo n = last [x | x <- primeFactors n]
  2. rebgongor
    import Data.Numbers.Primes
     
    mayorDivisorPrimo :: Integer -> Integer
    mayorDivisorPrimo = maximum . primeFactors
     
    -- λ> mayorDivisorPrimo 152416333181401
    -- 12345701
    -- (7.38 secs, 5,477,030,632 bytes)
  3. juaromsan5
    import Data.Numbers.Primes (primeFactors)
     
    mayorDivisorPrimo :: Integer -> Integer
    mayorDivisorPrimo = maximum . primeFactors
    • pabquirod

      En Python

      from sympy.ntheory import primefactors
       
      def mayorDivisorPrimo(n):
          return max(primefactors(n))
  4. jostircar1
    mayorDivisorPrimo:: Integer -> Integer
    mayorDivisorPrimo x = last [n | n <- [1..x], esprimo n, x `rem` n == 0]
     
    esprimo:: Integer -> Bool
    esprimo a = [z | z <- [1..a], a `rem` z == 0] == [1,a]
    • pabquirod

      En Python

      def divisores(n):
          """
          es la lista de los divisores de n. Por ejemplo,
             >>> divisores(30)
             [1, 2, 3, 5, 6, 10, 15, 30]
          """
          return [x for x in range(1, n+1) if n % x == 0]
       
       
      def esPrimo(n):
          """
          se verifica si n es primo. Por ejemplo,
             >>> esPrimo(7)
             True
             >>> esPrimo(8)
             False
          """
          return divisores(n) == [1, n]
       
       
      def mayorDivisorPrimo(n):
          return [x for x in divisores(n) if esPrimo(x)][-1]

Leave a Reply

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