Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

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.

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

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

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading