Python: Prime factorization base on sieve of Eratosthenes.

prime_factorization.py

def prime_factorization(x):
    import math
    if x == 0:
        return None

    seq = [None] * (x + 1)
    seq[1] = 1
    sqrt = int(math.sqrt(x))
    
    # Base on sieve of Eratosthene.Get store smallest prime factor.
    # if index is prime,the value is empty.
    for i in range(2, sqrt+1):
        if not seq[i]:
            start = int(math.pow(i, 2))
            for j in range(start, x + 1, i):
                seq[j] = i # store smallest prime factor(index is composite).

    # prime factorization
    f = []
    while not (x == 1) :
        a = seq[x] if seq[x] else x # if value is empty, assign x. 
        f.append(a)
        x = int( x / a)
    return f

for i in range(21):
    print(i, prime_factorization(i))


"""
0 None
1 []
2 [2]
3 [3]
4 [2, 2]
5 [5]
6 [2, 3]
7 [7]
8 [2, 2, 2]
9 [3, 3]
10 [2, 5]
11 [11]
12 [3, 2, 2]
13 [13]
14 [2, 7]
15 [3, 5]
16 [2, 2, 2, 2]
17 [17]
18 [3, 2, 3]
19 [19]
20 [2, 2, 5]
"""

JavaScript implementation: https://gist.github.com/ShenTengTu/1d314bf2be0ca46d9277ccfe1978dd6b