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.
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]
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).
