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