La implementación de un método de factorización en Haskell

Question

pregunta 266 en el Proyecto Euler y después de un poco de buscar, encontrado este método encontrar de forma rápida los factores de un número. Lo que se hace es encontrar todas las permutaciones de los factores primos de un número:. Estos son sus factores

Ya tengo un módulo para encontrar los factores de potencia primos de un número, por ejemplo:

Main> primePowerFactors 196
[(2,2),(7,2)]

Esto está demostrando básicamente que: 2^2 * 7^2 == 196. Desde aquí quiero encontrar todas las permutaciones de esos poderes, para dar los factores de 196 así:

• (2 ^ 0) (7 ^ 0) = 1
• (2 ^ 1) (7 ^ 0) = 2
• (2 ^ 2) (7 ^ 0) = 4
• (2 ^ 0) (7 ^ 1) = 7
• (2 ^ 1) (7 ^ 1) = 14
• (2 ^ 2) (7 ^ 1) = 28
• (2 ^ 0) (7 ^ 2) = 49
• (2 ^ 1) (7 ^ 2) = 98

Se me ocurrió lo siguiente:

factors n = [a|a<-map facs (primePowerFactors n), y <- [0..(snd $ last $ primePowerFactors n)]]
 where 
  facs (x,y) = (x,y)   
rSq n = toInteger $ round $ sqrt (fromInteger n)    
psr n = last $ dropWhile (<= rSq n) $ factors n
p = foldl' (*) 1 $ takeWhile (< 190) primes
answer = (psr p) `mod` (10^16)

Pero mi problema es que factors no funciona correctamente. Quiero que permutar a través de todos los posibles valores del exponente para cada factor primero y luego encontrar el producto para dar el factor. ¿Cómo puede ser modificado para devolver los pocos factores de los n

Answer 1

durante algún campo de código que he escrito una buena función de ajuste de potencia que es bastante simple.

powerSet [] = []
powerSet (x:xs) = xs : map (x:) (powerSet xs) ++ (powerSet xs)

Una deficiencia de este algoritmo es que no incluye el conjunto original, sin embargo, que es perfecto para usted, ya que no se ve como lo desee.

combinar esto con una forma de convertir su primePowerFactors n en una lista de enteros, digamos

ppfToList = concatMap (\(x,y)->replicate y x)

usando estos ayudantes, se genera una lista de factores de un número n con

factors n = nub . map product . powerSet . ppfToList . primePowerFactors $ n
-- will be out of order, you can add a call to `sort` to fix that

Este tipo de algoritmo es probablemente un poco más difícil de expresar en términos de una lista por comprensión.

Answer 2

En primer lugar, facs es la función identidad:

facs (x,y) = (x,y)

El y está ligada en el ajuste de patrones en el lado de la mano izquierda, mientras que es probable que pretende que sea la y de la lista comprensión. Los nombres de variable de la envolvente en una lista por comprensión son locales de que la comprensión y no se pueden utilizar en un ámbito diferente, como la cláusula where.

Además, el y en la lista de comprensión solamente se calcula a partir del exponente últimos factores:

y <- [0..(snd $ last $ primePowerFactors n)]

Para cada factor de su propio exponente debe ser considerado, no sólo siempre el exponente del factor pasado.

Un problema más fundamental es que el tipo de retorno de la función factors no parece coincidir es la intención:

*Euler> :t factors
factors :: Integer -> [(Integer, Int)]

Esto devuelve una lista de potencias de factores primos mientras que debería producir una lista de estas construcciones, como esto:

[
   [(2,0), (7,0)],
   [(2,1), (7,0)],
   [(2,2), (7,0)],
   [(2,0), (7,1)],
   [(2,1), (7,1)],
   ...
]

Se necesita la descomposición en factores primos de todos los factores posibles, pero la función parece volver sólo una descomposición en factores primos.