#! /usr/bin/env python | |
# Factorize numbers. | |
# The algorithm is not efficient, but easy to understand. | |
# If there are large factors, it will take forever to find them, | |
# because we try all odd numbers between 3 and sqrt(n)... | |
import sys | |
from math import sqrt | |
def fact(n): | |
if n < 1: | |
raise ValueError('fact() argument should be >= 1') | |
if n == 1: | |
return [] # special case | |
res = [] | |
# Treat even factors special, so we can use i += 2 later | |
while n % 2 == 0: | |
res.append(2) | |
n //= 2 | |
# Try odd numbers up to sqrt(n) | |
limit = sqrt(n+1) | |
i = 3 | |
while i <= limit: | |
if n % i == 0: | |
res.append(i) | |
n //= i | |
limit = sqrt(n+1) | |
else: | |
i += 2 | |
if n != 1: | |
res.append(n) | |
return res | |
def main(): | |
if len(sys.argv) > 1: | |
source = sys.argv[1:] | |
else: | |
source = iter(raw_input, '') | |
for arg in source: | |
try: | |
n = int(arg) | |
except ValueError: | |
print arg, 'is not an integer' | |
else: | |
print n, fact(n) | |
if __name__ == "__main__": | |
main() |