Menu
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.
608
Example of Factorial The prime decomposition of 20! is given as: 20! =218×38×54×72×11×13×17×19.
A factorial prime is a prime number that is one less or one more than a factorial (all factorials greater than 1 are even). The first 10 factorial primes (for n = 1, 2, 3, 4, 6, 7, 11, 12, 14) are (sequence A088054 in the OEIS): 2 (0!
In fact, (n/e)n according to Stirling's approximation. The prime factors of a factorial number, however, are all relatively small, and the complete factorization of n! n! n! is quite easy to obtain.
1 Consider the given number as the root of the tree 2 Write down the pair of factors as the branches of a tree 3 Again factorize the composite factors, and write down the factors pairs as the branches 4 Repeat the step, until to find the prime factors of all the composite factors
Prime Factorization Methods. The most commonly used prime factorization methods are: Division Method; Factor Tree Method; Division Method. The steps to calculate the prime factors of a number is similar to the process of finding the factors of a large number. Follow the below steps to find the prime factors of a number using the division method:
Prime Factorization. Prime Numbers. A Prime Number is: The first few prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19 and 23, and we have a prime number chart if you need more. If we can make it by multiplying other whole numbers it is a Composite Number. Here we see it in action: 2 is Prime, 3 is Prime, 4 is Composite (=2×2), 5 is Prime, and so on...
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:
156
Consider e.g. 33!. It's a product of:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
the factors are:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
2 2 2 2
2 2
2
3 3 3 3 3 3 3 3 3 3 3
3 3 3
3
5 5 5 5 5 5
5
7 7 7 7
11 11 11
13 13
17
19
23
29 31
Do you see the pattern?
33! = 2^( 33 div 2 + 33 div 4 + 33 div 8 + 33 div 16 + 33 div 32) *
3^( 33 div 3 + 33 div 9 + 33 div 27) *
5^( 33 div 5 + 33 div 25) *
----
7^( 33 div 7) * 11^( 33 div 11) * 13^( 33 div 13) *
----
17 * 19 * 23 * 29 * 31
Thus, to find prime factorization of n! without doing any multiplications or factorizations, we just need to have the ordered list of primes not greater than n, which we process (with a repeated integer division and a possible summation) in three stages - primes that are smaller or equal to the square root of n; such that are smaller or equal to n/2; and the rest.
Actually with lazy evaluation it's even simpler than that. Assuming primes is already implemented returning a stream of prime numbers in order, in Haskell, factorial factorization is found as
ff n = [(p, sum . takeWhile (> 0) . tail . iterate (`div` p) $ n)
| p <- takeWhile (<= n) primes]
-- Prelude> ff 33
-- [(2,31),(3,15),(5,7),(7,4),(11,3),(13,2),(17,1),(19,1),(23,1),(29,1),(31,1)]
because 33 div 4 is (33 div 2) div 2, etc..
26
2^3 is another way of writing 23, or two to the third power. (2^3)(3^1)(5^1) = 23 × 3 × 5 = 120.
(2^3)(3^1)(5^1) is just the prime factorization of 120 expressed in plain ASCII text rather than with pretty mathematical formatting. Your assignment requires output in this form simply because it's easier for you to output than it would be for you to figure out how to output formatted equations (and probably because it's easier to process for grading).
The conventions used here for expressing equations in plain text are standard enough that you can directly type this text into google.com or wolframalpha.com and it will calculate the result as 120 for you: (2^3)(3^1)(5^1) on wolframalpha.com / (2^3)(3^1)(5^1) on google.com
WolframAlpha can also compute prime factorizations, which you can use to get test results to compare your program with. For example: prime factorization of 1000!
A naïve solution that actually calculates the factorial will only handle numbers up to 12 (if using 32 bit ints). This is because 13! is ~6.2 billion, larger than the largest number that can be represented in a 32 bit int.
However it's possible to handle much larger inputs if you avoid calculating the factorial first. I'm not going to tell you exactly how to do that because either figuring it out is part of your assignment or you can ask your prof/TAs. But below are some hints.
ab × ac = ab+c
equation (a) 10 = 21 × 51
equation (b) 15 = 31 × 51
10 × 15 = ? Answer using the right hand sides of equations (a) and (b), not with the number 150.
10 × 15 = (21 × 51) × (31 × 51) = 21 × 31 × (51 × 51) = 21 × 31 × 52
As you can see, computing the prime factorization of 10 × 15 can be done without multiplying 10 by 15; You can instead compute the prime factorization of the individual terms and then combine those factorizations.
31
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
