def smallest_factor(n):   #n is an integer
    """if n is 1, return 1
    returns the smallest positive factor of n larger than 1."""
    if n < 0:
        n = -n
    if n%2 == 0:
        return 2
    factor = 3
    while n % factor > 0 and factor*factor <= n:
        factor += 2
    return factor if factor*factor <= n else n
def factorial(n):
    if n in [0, 1]:
        return 1
    out = 1
    for k in range(1, n + 1):
        out *= k
    return out
def prime_factorization(n):
    if n < 0:
        n = -n
    if n == 1:
        return []
    d = smallest_factor(n)
    return [d] + prime_factorization(n//d)
def prime_factorization_loop(n):
    if n < 0:
        n = -n
    if n == 1:
        return []
    out = []
    while n > 1:
        d = smallest_factor(n)
        out.append(d)
        n //= d
    return out
        

print(smallest_factor(111) == 3)
print(smallest_factor(37) == 37)
print(smallest_factor(215) == 5)
print(smallest_factor(38) == 2)
print(smallest_factor(1000000007))
print(prime_factorization_loop(111))
print(prime_factorization_loop(37))
print(prime_factorization_loop(215))
print(prime_factorization_loop(38))
print(prime_factorization_loop(1000000007))