Hacer una lista de divisores en Haskell

Question

Estoy haciendo el problema 21 en eulerproject. Una parte requiere encontrar la lista de divisores adecuados de un número. es decir, donde hay un resto de n y una cantidad inferior a n. Así que hice este Haskell, pero GHCI se enoja conmigo.

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

El problema es que no sé cómo hacer:

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

de modo que sólo devuelve el número menor que n que dividen uniformemente en n.

Answer 1

Solo necesita una variable separada.

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] 

Ahora, si usted quiere que sea un poco más eficiente, ya sabemos que un divisor no será más de la mitad de n, y sabemos que 1 es un divisor de todo. Y, vamos a seguir adelante y hacerlo un poco más Haskell-y para arrancar, evitando una lista de comprensión:

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] 

Answer 2

Si el orden de la lista de divisores no es importante, se puede hacer de este significativamente más eficiente en sólo verificando divisores en el rango [2..sqrt n].

Algo como esto (que probablemente podría hacer algunas optimizaciones locales si pensaba en ello más):

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

Dónde divisores es la aplicación anterior y divisores es el nuevo:

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

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

NOTA: Usamos nub para eliminar cualquier repetición, cuando de hecho la única repetición posible sería el límite, si n es un número cuadrado. Podrías hacerlo un poco más eficiente manejando mejor este caso, pero me parece que es más legible (si el tiempo de ejecución no es crítico).