"""This module provides some basic number-theoretic
functions."""
def gcd(a,b):
    """
    a:int
    b:int
    returns:  The greatest common divisor of a and b
    throws: ValueError if a == 0 && b == 0
    """
    if a == 0 and b == 0:
        raise ValueError
    if a < 0:
        a = -a
    if b < 0:
        b = -b
    if a == 0:
        return abs(b)
    if b == 0:
        return abs(a)
    while b%a > 0:
        b, a = a, b%a
    return a
def smallest_factor(n):
    """
    n:int    n should satisfy n >= 2
    returns: the smallest factor of n that is at least 2.
    """

    if n%2 == 0:
        return 2
    k = 3
    while k*k <= n:
        if n%k == 0:
            return k
        k += 2
    return n
def prime_factorization(n):
    """
    n: int  n should satisfy n >= 2
    returns: a list containing the prime factors of 
        n in ascending order
    """
    out = []
    while n > 1:
        d = smallest_factor(n)
        print(d)
        n = n//d
        out.append(d)
    return out
def is_prime(n):
    """
    n: int  n should satisfy n >= 2
    returns: True if n is a prime number
    """
    if n%2 == 0:
        return 2
    k = 3
    while k*k <= n:
        if n%k == 0:
            return False
        k += 2
    return True

#def primes_to(n):
#    out = [2]
#    k = 3
#    while k <= n:
#        j = 0
#        while out[j]*out[j] <= k:
#            if k%out[j] == 0:
#                j += 1
#                break
#            j += 1
#            out.append(k)
#        k += 2
#    return out

if __name__ == "__main__":
    #print(gcd(7776, 1048576))
    #print(gcd(95238908341908231432498324980875, 34904249809812494329625))
    #print(prime_factorization(1048575))
    #print(is_prime(1000009))
    #print(prime_factorization(1000009))
    print(primes_to(10000))