Search code examples
haskellfunctional-programmingprimes

Haskell - function that returns the sum of all prime divisors of a given number


this is my code, but it gives me an infinitive loop. i can't find my mistake, can you help me and give me some advices to find it?

isPrime :: Int -> Bool
isPrime n = n > 1 && helper 2
 where
    helper d
     | d >= n = True
     | mod n d == 0 = False
     | otherwise = helper (d + 1)

sumPrimeDivs :: Int -> Int
sumPrimeDivs n = helper n 2 0
 where
    helper num d result
     |isPrime d && mod num d == 0  = helper num (d + 1) result + d
     |d == num = result
     |otherwise = helper num (d + 1) result

I have to find the sum of all prime divisors of a given number.


Solution

  • The issue is in the last helper function. Sometimes we call helper p p result where the two first arguments are the same prime p. This falls in the first case of the definition

     |isPrime d && mod num d == 0  = helper num (d + 1) result + d
    

    This makes a recursive call to the helper with helper p (p+1) result but now the second argument is too large to trigger the termination condition

     |d == num = result
    

    Change that to d >= num instead.

    Further in the helper you never change the first and third arguments, so you can omit them. For instance:

    sumPrimeDivs :: Int -> Int
    sumPrimeDivs n = helper 2
     where
        helper d
         | isPrime d && mod n d == 0 = helper (d + 1) + d
         | d >= n                    = 0
         | otherwise                 = helper (d + 1)
    

    (Personally, I'd write the code differently, reordering the cases, making use of list comprehensions, or even using a more efficient algorithm, but I wanted to preserve your original code as much as possible here.)

    Alternatively, you might have wanted to use result as an accumulator, but in that case you need to call helper (d+1) (result+d) when you recurse.