factors.py

#!/usr/bin/env python
#
# Find & show factorization.
# Author:  Yotam Medini  [email protected] -- Created: 2006/January/30
#

import sys

def gcd(m, n):
    if m < n:
        t = m;  m = n;  n = t; # swap
    # Now we have:  m >= n >= 0
    while n > 0: # Euclid
        remainder = m % n
        m = n
        n = remainder
    return m


def lcm(m, n):
    return (m*n)/gcd(m, n)


def factorize(n):
    factors = []
    b = 2
    curr_divisor = 0; # strt with dummy
    while n > 1:
        if n % b == 0:
            if b == curr_divisor:
                # We already divided n by b.
                # So we look at the last 2-tuple, 
                # and increase the power by 1.  (b,p) ===>  (b,p+1)
                last_bp = factors[-1]
                bp = (b, last_bp[1] + 1)
                factors[-1] = bp
            else:
                # We got a new prime divisor!
                factors += [(b,1)]
                curr_divisor = b
            n /= b   # Exacly like:   n = n / b
        else:
            b += 1   # try another divisor
    return factors


def factors2str(factors_list):
    if len(factors_list) == 0:
        s = "2^0"
    else:
        s = ""
        pre_mult = ""
        for bp in factors_list:
            b = bp[0]
            p = bp[1]
            b_power_p = "%d^%d" % (b, p)
            s += pre_mult + b_power_p
            pre_mult = " * "
    return s


def factors_show(n, name):
    fl = factorize(n)
    fs = factors2str(fl)
    sys.stdout.write("%-8s = %18d = %s\n" % (name, n, fs))


def usage_exit(a0, rc):
    sys.stderr.write(
"""
Usage:
  %s <number1> <number2>
"""[1:] % a0)
    sys.exit(rc)


# Begin program
if len(sys.argv) != 3:
    usage_exit(sys.argv[0], 1)
a = int(sys.argv[1])
b = int(sys.argv[2])
factors_show(a, "a")
factors_show(b, "b")
factors_show(a*b, "ab")
factors_show(gcd(a,b), "gcd(a,b)")
factors_show(lcm(a,b), "lcm(a,b)")
    
sys.exit(0)