Prime Factorization & Divisibility

primefactorization.py

#!/usr/bin/python3.2
import sys

def gen_primes():
    """ Generate an infinite sequence of prime numbers.
    """
    # Maps composites to primes witnessing their compositeness.
    # This is memory efficient, as the sieve is not "run forward"
    # indefinitely, but only as long as required by the current
    # number being tested.
    #
    D = {}  

    # The running integer that's checked for primeness
    q = 2  

    while True:
        if q not in D:
            # q is a new prime.
            # Yield it and mark its first multiple that isn't
            # already marked in previous iterations
            # 
            yield q        
            D[q * q] = [q]
        else:
            # q is composite. D[q] is the list of primes that
            # divide it. Since we've reached q, we no longer
            # need it in the map, but we'll mark the next 
            # multiples of its witnesses to prepare for larger
            # numbers
            # 
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]

        q += 1
        
def get_prime_divisors(n):
    divs = []
    primes = []

    # Make the primes
    for x in gen_primes():
        primes.append(x)
        if x > n:
            break

    num = n
    while num > 1:
        for x in primes: 
            if num % x == 0:
                # If divisible by the prime, add it to our prime
                # factorization list
                divs.append(x)
                num = num / x
                break
            else:
                continue
    
    return divs

def or_lists(a, b):
    new = []
    for x in a:
        if x in b:
            new.append(x)
            a.pop(x)
            b.pop(x)
    new.extend(a)
    new.extend(b)
    return new
               

if len(sys.argv) > 2:
    union = []
    for x in sys.argv[1:]:
        divs = get_prime_divisors(int(x))
        print("The prime factorization of {1} is: {0}".format(
        divs, int(x)))
        union = or_lists(divs, union)
    print(union)
else:
    print("The prime factorization of {1} is: {0}".format(
        get_prime_divisors(int(sys.argv[1])), int(sys.argv[1])))