Implementare un procedimento fattorizzazione in Haskell

Question

domanda 266 a Project Euler e dopo un po 'di la ricerca, ha trovato questo metodo individuazione dei rapidamente i fattori di un numero. Quello che fate è trovare tutte le permutazioni dei fattori primi di un numero:. Questi sono i suoi fattori

Ho già un modulo per trovare i fattori di potenza primi di un numero, ad esempio:

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

Questo è fondamentalmente dimostrando che: 2^2 * 7^2 == 196. Da qui voglio trovare tutte le permutazioni di tali competenze, a dare i fattori di 196 nel seguente modo:

• (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

Sono venuto con la seguente:

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)

Ma il mio problema è che factors non funziona correttamente. Voglio che per permutare attraverso tutti i possibili valori di esponente per ogni fattore primo e poi trovare il prodotto per dare il fattore. Come può essere modificato per restituire i giusti fattori di n

Answer 1

per un po 'di golf codice che ho scritto un bel funzione set potere che è piuttosto semplice.

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

Una carenza di questo algoritmo è che non include la serie originale, tuttavia, che è perfetto per voi in quanto non guardare come si desidera.

combinare questo con un modo per convertire il vostro primePowerFactors n in una lista di interi, diciamo

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

utilizzando questi aiutanti, un elenco di fattori da un numero n è generato 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

Questo tipo di algoritmo è probabilmente un po 'più difficile da esprimere in termini di una lista di comprensione.

Answer 2

Prima di tutto, facs è la funzione identità:

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

Il y è legato nel match modello sul lato sinistro, mentre probabilmente si voleva che fosse il y dalla lista comprensione. I nomi delle variabili legate in una list comprehension sono locali a quella comprensione e non possono essere utilizzate in un ambito diverso, come la clausola where.

Inoltre, il y nella lista di comprensione viene calcolata solo dal ultimi fattori dell'esponente:

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

Per ogni fattore è proprio esponente deve essere considerata, non solo sempre l'esponente del ultimo fattore.

Un problema più fondamentale è che il tipo di ritorno della funzione factors non sembra corrispondere è intenzione:

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

Questo restituisce un elenco di potenze di fattori primi mentre dovrebbe produrre un elenco di questi costrutti, in questo modo:

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

È necessaria la scomposizione in fattori primi di tutti i possibili fattori, ma la funzione sembra tornare solo una fattorizzazione in numeri primi.