The goal of this challenge is to decompose n! (factorial n) into its prime factors. The function decomp(n) should return the decomposition of n! into its prime factors in increasing order of the primes, as a string. The factorial can be a very big number (4000! has 12674 digits, n will go from 300 to 4000).

Examples:
n = 12; decomp(12) -> "2^10 * 3^5 * 5^2 * 7 * 11"
since 12! is divisible by 2 ten times, by 3 five times, by 5 two times and by 7 and 11 only once.

n = 22; decomp(22) -> "2^19 * 3^9 * 5^4 * 7^3 * 11^2 * 13 * 17 * 19"
n = 25; decomp(25) -> 2^22 * 3^10 * 5^6 * 7^3 * 11^2 * 13 * 17 * 19 * 23

Prime numbers should be in increasing order. When the exponent of a prime is 1 don't write the exponent.

Tests:
decomp(17)
decomp(5)
decomp(22)
decomp(14)
decomp(25)

Good luck!

This challenge comes from g964 on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!