Haskell get divisors efficiently

Question

I want to efficiently find the proper divisors of an integer n.

How can I do this?

For now I´m using the following function

divisors :: (Integral a) => a -> [a]
divisors n = filter ((0 ==) . (n `mod`)) [1 .. (n `div` 2)]

But I have read that it is more efficient when I only check for the numbers until the square root of n. Have you got any suggestions how to solve it with the square root?

Your current function checks all numbers up to half of `n`, and you want to change it so it checks up to the square root of `n` instead? I'm pretty confident that you can work out for yourself how to change your function to do that. — Robin Zigmond, Oct 19 '19 at 20:41

score -1 · Answer 1 · answered Oct 19 '19 at 20:43

Given a number n is dividable by k, then n/k is a divisor of n as well. Indeed, since n/(n/k)=k. If k>√n, we thus know that k/n<√n, and therefore, instead of calculating all the divisors, we can each time we find a divisor, yield the "co-divisor" as well.

We thus can implement the algorithm as follows:

divisors :: Integral a => a -> [a]
divisors n = concatMap f (filter ((==) 0 . mod n) (takeWhile (\k -> k*k <= n) [1 .. n]))
    where f k | k < l = [k, l]
              | otherwise = [k]
              where l = div n k

Here we thus first use takeWhile (\k -> k*k <= n) [1 .. n] to create a list from 1 until (and including if it is integral) √n).

Next we filter these elements, and only retain those that divide n. Finally for each of these elements, we check if the co-divisor is different. If that is the case, we both yield k and the co-divisor l, otherwise (this will only be the case for √n), we only yield k.

For example:

Prelude Data.List> divisors 1425
[1,1425,3,475,5,285,15,95,19,75,25,57]

Haskell get divisors efficiently

1 Answers1