Making a list of divisors in Haskell

Question

I am doing problem 21 in eulerproject. One part requires finding the list of proper divisors of a number. i.e. where there is remainder of n and some number of less than n. So I made this Haskell, but GHCI gets angry at me.

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

The problem is that I don't know how to make:

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

so that it only returns the number less than n that divide evenly into n.

Answer 1

You just need a separate variable.

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]

Now, if you wanted to make it a bit more efficient, we already know that a divisor won't be more than half of n, and we know 1 is a divisor of everything. And, let's go ahead and make it a bit more Haskell-y to boot, avoiding a list comprehension:

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

If the order of the list of divisors is not important, you can make this significantly more efficient by only checking divisors in the range [2..sqrt n].

Something like this (you could probably make some local optimisations if you thought about it more):

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

Where divisors is the previous implementation, and divisors' is the new one:

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

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

NOTE: We I used nub to remove any repetitions, when in fact the only possible repetition would be limit, if n is a square number. You could make it slightly more efficient by handling this case better, but I find this way is more readable (if running time isn't critical).