2009-09-26 4 views
10

Sto facendo il problema 21 in eulerproject. Una parte richiede la ricerca dell'elenco dei divisori appropriati di un numero. vale a dire dove c'è il resto di n e un numero inferiore a n. Così ho fatto questo Haskell, ma GHCI si arrabbia con me.Creazione di un elenco di divisori in Haskell

divisors n =[ n | n <- [1..(n-1)], n `rem` [1..(n-1)] ==0 ] 

Il problema è che non so come fare:

n `rem` [1..(n-1)] 

in modo che restituisca solo il numero a meno di n che divide in modo uniforme in n.

risposta

17

Hai solo bisogno di una variabile separata.

Prelude> let divisors n = [x | x <- [1..(n-1)], n `rem` x == 0] 
Prelude> divisors 20 
[1,2,4,5,10] 
Prelude> divisors 30 
[1,2,3,5,6,10,15] 

Ora, se si voleva fare un po 'più efficiente, sappiamo già che un divisore, non sarà più della metà dei n, e sappiamo 1 è un divisore di tutto. E, andiamo avanti e fare un po 'più Haskell-y per l'avvio, evitando una lista di comprensione:

Prelude> let divisors n = 1 : filter ((==0) . rem n) [2 .. n `div` 2] 
Prelude> divisors 20 
[1,2,4,5,10] 
Prelude> divisors 30 
[1,2,3,5,6,10,15] 
Prelude> divisors 31 
[1] 
+3

Perché la comprensione delle liste non è molto Haskell? Inoltre, una piccola domanda, c'è un modo per trovare la somma della somma di tutte le liste in una lista? –

+0

Non sono un veterano di Haskell con qualsiasi mezzo, ma non ho visto alcuna comprensione delle liste usata in nessuna libreria di Haskell, per esempio. Risposta piccola: 'sum $ map sum x', come' sum $ map sum [[1,2,3], [4,5,6], [7,8,9]] 'risultante in 45. –

+0

Oppure 'somma. concat', che per prima fa una grande lista. –

7

Se l'ordine della lista dei divisori non è importante, si può fare questo molto più efficiente da solo controllando i divisori nell'intervallo [2..sqrt n].

Qualcosa di simile (probabilmente si potrebbe fare alcune ottimizzazioni locali se si pensa a questo proposito più):

divisors' n = (1:) $ nub $ concat [ [x, div n x] | x <- [2..limit], rem n x == 0 ] 
    where limit = (floor.sqrt.fromIntegral) n 

Dove divisori è l'implementazione precedente e divisori è il nuovo:

*Main> (sum.divisors) 10000000 
14902280 
(4.24 secs, 521136312 bytes) 

*Main> (sum.divisors') 10000000 
14902280 
(0.02 secs, 1625620 bytes) 

NOTA: Abbiamo usato nub per rimuovere eventuali ripetizioni, quando in realtà l'unica ripetizione possibile sarebbe il limite, se n è un numero quadrato. Potresti renderlo leggermente più efficiente gestendo meglio questo caso, ma trovo che questo modo sia più leggibile (se il tempo di esecuzione non è critico).