Factores primos en Haskell

Luego de de una prolongada recopilación de información resolvimos esta interrogante que tienen algunos de nuestros usuarios. Te ofrecemos la solución y deseamos servirte de mucha ayuda.

Solución:

Un método simple para determinar los factores primos de n Es para

• buscar el primer divisor d en [2..n-1]
• si D existe: volver d : primeFactors(div n d)
• de lo contrario volver n (ya que n es primo)

Código:

prime_factors :: Int -> [Int]

prime_factors 1 = []
prime_factors n
  | factors == []  = [n]
  | otherwise = factors ++ prime_factors (n `div` (head factors))
  where factors = take 1 $ filter (x -> (n `mod` x) == 0) [2 .. n-1]

Obviamente, esto podría usar mucha optimización (buscar solo de 2 a sqrt (N), almacenar en caché los números primos encontrados hasta ahora y calcular la división solo para estos, etc.)

ACTUALIZAR

Una versión ligeramente modificada usando el caso (según lo sugerido por @ user5402):

prime_factors n =
  case factors of
    [] -> [n]
    _  -> factors ++ prime_factors (n `div` (head factors))
  where factors = take 1 $ filter (x -> (n `mod` x) == 0) [2 .. n-1]

Esta es una implementación de buen rendimiento y fácil de entender, en la que isPrime y primes se definen recursivamente, y primes se almacenará en caché de forma predeterminada. primeFactors la definición es solo un uso apropiado de primesel resultado contendrá números duplicados continuos, esta característica facilita contar el número de cada factor a través de (map (head &&& length) . group) y es fácil identificarlo a través de (map head . group) :

isPrime :: Int -> Bool
primes :: [Int]

isPrime n | n < 2 = False
isPrime n = all (p -> n `mod` p /= 0) . takeWhile ((<= n) . (^ 2)) $ primes
primes = 2 : filter isPrime [3..]

primeFactors :: Int -> [Int]
primeFactors n = iter n primes where
    iter n (p:_) | n < p^2 = [n | n > 1]
    iter n [email protected](p:ps') =
        let (d, r) = n `divMod` p
        in if r == 0 then p : iter d ps else iter n ps'

Y el uso:

> import Data.List
> import Control.Arrow

> primeFactors 12312
[2,2,2,3,3,3,3,19]

> (map (head &&& length) . group) (primeFactors 12312)
[(2,3),(3,4),(19,1)]

> (map head . group) (primeFactors 12312)
[2,3,19]

Hasta el dividendo m < 2,

1. toma el primer divisor n de primos.
2. repetir dividir m por n mientras que divisible.
3. tomar el siguiente divisor n de primos, y vaya a 2.

La lista de todos los divisores realmente usados ​​son factores primos del original m.

Código:

-- | prime factors
--
-- >>> factors 13
-- [13]
-- >>> factors 16
-- [2,2,2,2]
-- >>> factors 60
-- [2,2,3,5]
--
factors :: Int -> [Int]
factors m = f m (head primes) (tail primes) where
  f m n ns
    | m < 2 = []
    | m `mod` n == 0 = n : f (m `div` n) n ns
    | otherwise = f m (head ns) (tail ns)

-- | primes
--
-- >>> take 10 primes
-- [2,3,5,7,11,13,17,19,23,29]
--
primes :: [Int]
primes = f [2..] where f (p : ns) = p : f [n | n <- ns, n `mod` p /= 0]

Actualizar:

Este código de reemplazo mejora el rendimiento al evitar evaluaciones innecesarias:

factors m = f m (head primes) (tail primes) where
  f m n ns
    | m < 2 = []
    | m < n ^ 2 = [m]   -- stop early
    | m `mod` n == 0 = n : f (m `div` n) n ns
    | otherwise = f m (head ns) (tail ns)

primes también se puede acelerar drásticamente, como se menciona en el comentario de Will Ness:

primes = 2 : filter (n-> head (factors n) == n) [3,5..]

Si te gusta este mundo, puedes dejar una sección acerca de qué te ha parecido esta crónica.

---

---

Utiliza Nuestro Buscador