Search code examples
listfunctionhaskellfactorization

Generate prime factors of a number

I'm trying to write a function that given an Int greater than one gives a non decreasing list made of the prime factors (with repetition) of that number

Example: n = 12, the output should be [2,2,3]

I don't know where to start.

Solution

  • There are of course well know algorithms for what you want to do, so simple google search would really solve that.

    However, I'd like to show you a simple thinking process that might be helpful in the future.

    Since the factors have to appear in the ascending order, you might:

    1. Start with the lowest prime (2).
    2. Check if the number can be divided by it. If it can, do it and go back to 1.
    3. If not, replace 2 with a next prime and go back to 2.

    Now, it's obvious that the biggest prime you will ever check is the number you've started with. However, the basic multiplication axiom states that if a number can be divided by a:

    n / a = b

    Then it can also be divided by b! You can use that fact to further narrow the checking range, but I'll leave it to you to figure (or google) the upper bound.

    Actual implementation is of course a part of your homework and thus supplying code wouldn't be a wise idea here. However, I don't think that stuff such as next_prime will be hard for you.