Clever Geek Handbook

Prime Factoring function in Haskell

I am trying to make a function that will display the number of simple factors with a (infinite) list I give it. Here's what I have so far:

-- Here is a much more efficient (but harder to understand) version of primes.
-- Try "take 100 primes" as an example (or even more if you like)
primes = 2 : primesFrom3 where 
    primesFrom3 = sieve [3,5..] 9 primesFrom3
    sieve (x:xs) b ~ps@(p:q:_)
      | x < b     = x : sieve xs b ps
      | otherwise =     sieve [x | x <- xs, rem x p /= 0] (q^2) (tail ps)



-- Write a function that factors its first argument using the (infinite)
-- list of available factors given in its second argument
-- (using rem x p /= 0 to check divisibility)
primeFactsWith :: Integer -> [Integer] -> [Integer]
primeFactsWith n (p:ps) = if (rem n p /= 0) then
                                (primeFactsWith n ps)
                          else (primeFactsWith p ps)

The top half was not written by me and works great. I'm trying to get the other half to work, but it doesn't. Read the comments in the code to get a better understanding of what I am trying to do. Thank you! Oh please don't just hand out the answer. Give me some hints on how to do this, and maybe what is wrong.

+3


source to share


2 answers


What happened

The problem is that you are doing a recursive call on both branches, so the function never stops.

Some hints

To create a recursive list creation function, you need two branches or cases:

  • Base register missing recursive call, this stops recursion and returns the final part of the result.
  • Recursive case here you change the parameters of the function and call it again with the changed parameters, possibly returning part of the result as well.


In a recursive branch, you will need two sub branches. One if you found a simple factor, and another if the current number is not a simple factor.

Here is the skeleton, you need to fill in the parts in brackets <>

.

primeFactsWith :: Integer -> [Integer] -> [Integer]
primeFactsWith n (p:ps) = if <halt condition> then
                            <final result>
                          else if (rem n p /= 0) then
                            <not a factor - recursive call 1>
                          else 
                            <found a factor - return it, 
                             and make recursive call 2>

  • If you find the main factor, you can divide it by it to get a lower number without this factor. To perform integer division, Haskell provides a function named div

    .

  • If you reach number 1, you have created all the basic factors and you can stop. The final part of the list of major factors, which comes after all its factors, is an empty list.

  • You can drop any prime from your infinite list if you no longer need it, but keep in mind that a number can contain a space multiple times in the factor list. If you want to opt out p

    , you can simply use ps

    , from the template; if you want to keep p

    , you must use (p:ps)

    .

  • The cons operator (:)

    can be used to create a list. You can use it to return one number of the list of results and use recursive call to find the remaining numbers for example.

    x : foo y z

I hope this helps, if you have any questions feel free to ask.

+4


source


Here's a hint.

So you're recursive, which is good.



In one branch, you keep looking for factors n

. On another thread, you seem to need to look for factors p

, which is a bit weird, but whatevs.

Where do you return the factors n

that you found?

0


source






More articles:


All Articles