divsfact.py

#!/usr/bin/env python
#
# Find divisors in show their factorization.
# Author:  Yotam Medini  [email protected] -- Created: 2006/February/26
#

import sys

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):
    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 = %8d = %s\n" % (name, n, fs))


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


# Begin program
if len(sys.argv) != 2:
    usage_exit(sys.argv[0], 1)
N = int(sys.argv[1])
factors_show(N, "N")
sys.stdout.write("Divisors:\n")
nd = 0
d = 1
while d <= N:         # Check all numbers d,  such that  1 <= d <= N
    if N % d == 0:
        # d is a divisor, so show it
        nd += 1
        name = " d[%2d]" % nd
        factors_show(d, name)
    d += 1
sys.stdout.write("%d has %d divisors\n" % (N, nd))
sys.exit(0)