List of divisors of an integer n (Haskell)

Posted by Code-Guru on Stack Overflow See other posts from Stack Overflow or by Code-Guru
Published on 2012-09-06T01:38:44Z Indexed on 2012/09/06 15:38 UTC
Read the original article Hit count: 236

Filed under:
|
|
|

I currently have the following function to get the divisors of an integer:

-- All divisors of a number
divisors :: Integer -> [Integer]
divisors 1 = [1]
divisors n = firstHalf ++ secondHalf
    where firstHalf = filter (divides n) (candidates n)
          secondHalf = filter (\d -> n `div` d /= d) (map (n `div`) (reverse firstHalf))
          candidates n = takeWhile (\d -> d * d <= n) [1..n] 

I ended up adding the filter to secondHalf because a divisor was repeating when n is a square of a prime number. This seems like a very inefficient way to solve this problem.

So I have two questions: How do I measure if this really is a bottle neck in my algorithm? And if it is, how do I go about finding a better way to avoid repetitions when n is a square of a prime?

© Stack Overflow or respective owner

Related posts about Performance

Related posts about haskell