The aim of the kata is to decompose `n!` (factorial n) into its prime factors.

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 put the exponent.

Notes

- the function is `decomp(n)` and should return the decomposition of `n!` into its prime factors in increasing order of the primes, as a string.
- factorial can be a very big number (`4000! has 12674 digits`, n will go from 300 to 4000).
- In Fortran - as in any other language - the returned string is not permitted to contain any redundant trailing whitespace: you can use `dynamically allocated character strings`.

Difficulty: introductory

Starter code:

def decomp(n):
	

Solutions:
from collections import defaultdict

def dec(n):
    decomp = defaultdict(lambda:0)
    i = 2
    while n > 1:
        while n % i == 0:
            n /= i
            decomp[i] += 1
        i += 1
    return decomp
            

def decomp(n):
    ans = defaultdict(lambda:0)
    for i in range(2, n + 1):
        for key, value in dec(i).items():
            ans[key] += value
    return ' * '.join('{}^{}'.format(x, y) if y > 1 else str(x) for x, y in sorted(ans.items()))

def decomp(chisl):
    
    div = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,
        163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,
        331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,
        503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,
        691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,
        887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,
        1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,
        1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,
        1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,
        1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,
        1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,
        1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,
        1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,
        1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,
        1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,
        1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,
        1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,2063,2069,
    2081,2083,2087,2089,2099,2111,2113,2129,2131,2137,2141,2143,
    2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,2267,
    2269,2273,2281,2287,2293,2297,2309,2311,2333,2339,2341,2347,
    2351,2357,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,
    2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,2539,2543,
    2549,2551,2557,2579,2591,2593,2609,2617,2621,2633,2647,2657,
    2659,2663,2671,2677,2683,2687,2689,2693,2699,2707,2711,2713,
    2719,2729,2731,2741,2749,2753,2767,2777,2789,2791,2797,2801,
    2803,2819,2833,2837,2843,2851,2857,2861,2879,2887,2897,2903,
    2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,3001,3011,
    3019,3023,3037,3041,3049,3061,3067,3079,3083,3089,3109,3119,
    3121,3137,3163,3167,3169,3181,3187,3191,3203,3209,3217,3221,
    3229,3251,3253,3257,3259,3271,3299,3301,3307,3313,3319,3323,
    3329,3331,3343,3347,3359,3361,3371,3373,3389,3391,3407,3413,
    3433,3449,3457,3461,3463,3467,3469,3491,3499,3511,3517,3527,
    3529,3533,3539,3541,3547,3557,3559,3571,3581,3583,3593,3607,
    3613,3617,3623,3631,3637,3643,3659,3671,3673,3677,3691,3697,
    3701,3709,3719,3727,3733,3739,3761,3767,3769,3779,3793,3797,
    3803,3821,3823,3833,3847,3851,3853,3863,3877,3881,3889,3907,
    3911,3917,3919,3923,3929,3931,3943,3947,3967,3989,4001]
    exp = [0] * len(div)           
    otvet = []  
    chislo = 1
    for i in range (1, chisl+1): 
        for ii in range(len(div)):
            while i % div[ii] == 0:
                i /= div[ii]
                exp[ii] += 1
    for ii in range(len(div)):            
        if exp[ii] > 1:
            otvet += [str(div[ii]) + '^' + str(exp[ii])]
        if exp[ii] == 1:
            otvet += [str(div[ii])]
    return(' * '.join(otvet))
    #your code here


def decomp(n):
    out = []
    for d in range(2, n+1):
        if d==2 or (d&1 and d>2 and all(d%i for i in range(3, 1+int(d**0.5), 2))):
            a, x = 0, n
            while x >= d:
                x //= d            
                a += x
            out.append((d,a))
    return ' * '.join([f'{i}^{j}' if j>1 else str(i) for i,j in out])


def decomp(n):
    f = {}
    for  i in range(2, n+1):
        for j in range(2, int(i**0.5)+1):
            while i%j==0:
                i = i//j
                if j in f: f[j] += 1
                else: f[j] = 1
        if i!=1:
            if i in f: f[i] += 1
            else: f[i] = 1
        
    return ' * '.join(["{}^{}".format(i, f[i]) if f[i]>1 else str(i) for i in sorted(f)])

from itertools import count

dec = [[],[],[1]]
primes = [2]

def genPrimes():
    for x in count(3,2):
        sq = int(x**.5)
        if all(p>sq or x%p for p in primes):
            yield x
    
primGen = genPrimes()

def genPrimesUpTo(n):
    while primes[-1] < n:
        primes.append(next(primGen))

def genPrimeDivs(n):
    genPrimesUpTo(n)
    dec.append(dec[-1][:])                                # Duplicate last factorial decomposition
    for i,p in enumerate(primes):
        while not n%p:
            n //= p
            while i >= len(dec[-1]): dec[-1].append(0) 
            dec[-1][i] += 1
            if n<2: break
    

def decomp(n):
    while len(dec) <= n:
        genPrimeDivs(len(dec))
    return " * ".join(str(p) if c==1 else "{}^{}".format(p,c) for p,c in zip(primes,dec[n]))

def decomp(n):
    result = []
    for i in primes():
        if i > n:
            break
        count = 0
        for j in range(2, n+1):
            while j % i == 0:
                count += 1
                j = j / i
        if count > 1:
            result.append(str(i)+'^'+str(count))
        else:
            result.append(str(i))
    return ' * '.join(result)

def primes():
    yield 2
    it = odd()
    while True:
        n = next(it)
        yield n
        it = filter(lambda x,n=n: x % n > 0, it)
        
def odd():
    n = 1
    while True:
        n += 2
        yield n

# What a f****** mess this was...

import math
import numpy as np

def decomp(n):   

    def rt(x):             
        if x % 2 == 0:
                return [2, int(x/2)]        
        for i in range(3, math.floor(math.sqrt(x)) + 1, 2):
                if x % i == 0:
                    return [i, int(x/i)]        
        return [x, 1]  
        
    leftovers = np.arange(2, n+1, 1)    
    facs = [0]*(n-1)
    
    while leftovers != []:
        newlefts = []
        
        for l in leftovers:
            [h, k] = rt(l)
            facs[h-2] += 1
            
            if k != 1:
                newlefts += [k]
        
            
        leftovers = newlefts    
    
    string = ''
    
    for m in range(2, n+1):
        if facs[m-2] == 1:
            if string != '':
                string += ' * ' + str(m)
            if string == '':
                string = str(m)
        if facs[m-2] > 1:
            if string != '':
                string += ' * ' + str(m) + '^' + str(facs[m-2])
            if string == '':
                string = str(m) + '^' + str(facs[m-2])
    
    
    
    return string
        
    
    
    

  























              
      
    
    
        
        
        
        
        
        
       



def primes(n):
    primes = [2]
    for i in range(3,n+1):
        if all(i%p!= 0 for p in primes) == True:
            primes.append(i)
    return(primes)
def decomp(n):
    prim = primes(n)
    factors = {}
    for i in range(2, n+1):
        if i in prim:
            factors[i] = 1
        else:
            for p in prim:
                while i%p == 0:
                    factors[p] += 1
                    i /= p
                if i == 1:
                    break
    res = ''
    for x, y in factors.items():
        res += '{0}^{1} * '.format(x,y) if y != 1 else '{0} * '.format(x)
    return(res[:-3])

is_prime = lambda n: n == 2 or n % 2 and all(n % d for d in range(3, int(n ** .5) + 1, 2))
order = lambda n, k: n and n // k + order(n // k, k)
decomp = lambda n: ' * '.join(str(p) if n < 2 * p else '%d^%d' % (p, order(n, p)) for p in range(2, n+1) if is_prime(p))

def decomp(n):
    primes = (2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861,2879,2887,2897,2903,2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,3001,3011,3019,3023,3037,3041,3049,3061,3067,3079,3083,3089,3109,3119,3121,3137,3163,3167,3169,3181,3187,3191,3203,3209,3217,3221,3229,3251,3253,3257,3259,3271,3299,3301,3307,3313,3319,3323,3329,3331,3343,3347,3359,3361,3371,3373,3389,3391,3407,3413,3433,3449,3457,3461,3463,3467,3469,3491,3499,3511,3517,3527,3529,3533,3539,3541,3547,3557,3559,3571,3581,3583,3593,3607,3613,3617,3623,3631,3637,3643,3659,3671,3673,3677,3691,3697,3701,3709,3719,3727,3733,3739,3761,3767,3769,3779,3793,3797,3803,3821,3823,3833,3847,3851,3853,3863,3877,3881,3889,3907,3911,3917,3919,3923,3929,3931,3943,3947,3967,3989)
    
    def proc(c,n):
        ct = 0
        q = 1
        while n >= q*c:
            q *= c
            ct += n//q
        return f'{c}^{ct}' if ct > 1 else str(c)
    
    return ' * '.join(proc(c,n) for c in primes if n >= c)

mults={}
def get_primes(n):
    prims=[True]*(n+1)
    prims[0]=False
    prims[1]=False
    #print(prims)
    for x in range(2,n-1):
        #print(prims)
        if(prims[x]):
            prims[x+x::x]=[False]*(n//x-1)
    return [x for x in range(len(prims)) if prims[x]]

def find_mults(n, p):
    if (n,p) in mults:
        return mults[n,p]
    if(n%p!=0):
        return 0
    if(n==p):
        return 1
    return 1+find_mults(n/p, p)

def get_mults(n,p):
    if (n,p) not in mults:
        mults[n,p]=find_mults(n,p)
    return mults[n,p]

def decomp(m):
    primes=get_primes(m+1)
    #print(primes)
    final_string=[]
    for p in [x for x in primes if x<=m]: #go through the primes once at a time
        s=0
        for n in range(p,m+1,p): #go through all numbers from p to m+1??? 
            
            s+=get_mults(n,p )
        if(s>0):
            if(s==1):
                final_string.append(str(p))
            else:
                final_string.append(str(p)+"^"+str(s))
        #print(s)
    #print(" * ".join(final_string))
    return " * ".join(final_string)