12

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.

Jonno_FTW
  • 8,601
  • 7
  • 58
  • 90

2 Answers2

18

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]
Mark Rushakoff
  • 249,864
  • 45
  • 407
  • 398
  • 4
    Why is list comprehension not very Haskell? Also, a small question, is there a way to find the sum of the sum of all the lists in a list? – Jonno_FTW Sep 26 '09 at 18:18
  • I'm not a Haskell veteran by any means, but I haven't really seen any list comprehensions used in any Haskell libraries, for instance. Small answer: `sum $ map sum x`, such as `sum $ map sum [ [1,2,3], [4,5,6], [7,8,9] ]` resulting in 45. – Mark Rushakoff Sep 26 '09 at 19:37
  • Or `sum . concat`, which first makes one big list. – Anschel Schaffer-Cohen Jun 04 '11 at 00:44
8

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

Greg
  • 81
  • 1
  • 2
  • The nub could be remove replacing [2 .. limit] by [2 .. limit-1], then consider limit as special case, if rem n limit == 0 if it's then add limit to the divisors – Yu Shen May 22 '20 at 03:18