algorithmmathprimesfactorialprime-factoring

Prime factorization of a factorial


I need to write a program to input a number and output its factorial's prime factorization in the form:

4!=(2^3)*(3^1)

5!=(2^3)*(3^1)*(5^1)

The problem is I still can't figure out how to get that result.

Apparently each first number in brackets is for the ascending prime numbers up until the actual factorial. The second number in brackets is the amount of times the number occurs in the factorial.

What I can't figure out is for example in 5!=(2^3)*(3^1)*(5^1), how does 2 only occur 3 times, 3 only 1 time and 5 only one time in 120 (5!=120).

I have now solved this thanks to the helpful people who commented but I'm now having trouble trying to figure out how could I take a number and get the factorial in this format without actually calculating the factorial.


Solution

  • Every number can be represented by a unique (up to re-ordering) multiplication of prime numbers, called the prime factorization of the number, as you are finding the prime factors that can uniquely create that number.

    2^3=8

    3^1=3

    5^1=5

    and 8*3*5=120

    But this also means that: (2^3)*(3^1)*(5^1) = 120

    It's not saying that 2 occurs 3 times as a digit in the number 120, which it obviously does not, but rather to multiply 2 by 2 by 2, for a total of 3 twos. Likewise for the 3 and 5, which occur once in the prime factorization of 120. The expression which you mention is showing you this unique prime factorization of the number 120. This is one way of getting the prime factorization of a number in Python:

    def pf(number):
        factors=[]
        d=2
        while(number>1):
            while(number%d==0):
                factors.append(d)
                number=number/d
            d+=1
        return factors
    

    Running it you get:

    >>> pf(120)
    [2, 2, 2, 3, 5]
    

    Which multiplied together give you 120, as explained above. Here's a little diagram to illustrate this more clearly:

    enter image description here