def divisors(N):
"""return the biggest prime divisor for numbers less than N"""
result = [1 for x in xrange(N)]
for d in xrange(2,N):
if result[d] > 1: continue
for j in xrange(d, N, d):
result[j] = d
return result
divs = divisors(2000)
def factor(n, divisors=divs):
result = []
while n > 1:
p = divisors[n]
if p == 1:
result.append(n)
return result
while n % p == 0:
result.append(p)
n /= p
return result
print 1000, factor(1000)
print 24, factor(24)
print 17*31, factor(17*31)
CmRlZiBkaXZpc29ycyhOKToKICAgICIiInJldHVybiB0aGUgYmlnZ2VzdCBwcmltZSBkaXZpc29yIGZvciBudW1iZXJzIGxlc3MgdGhhbiBOIiIiCiAgICByZXN1bHQgPSBbMSBmb3IgeCBpbiB4cmFuZ2UoTildCiAgICBmb3IgZCBpbiB4cmFuZ2UoMixOKToKCWlmIHJlc3VsdFtkXSA+IDE6ICBjb250aW51ZQogICAgICAgIGZvciBqIGluIHhyYW5nZShkLCBOLCBkKToKCQlyZXN1bHRbal0gPSBkCiAgICByZXR1cm4gcmVzdWx0CgoKZGl2cyA9IGRpdmlzb3JzKDIwMDApCgpkZWYgZmFjdG9yKG4sIGRpdmlzb3JzPWRpdnMpOgoJcmVzdWx0ID0gW10KCXdoaWxlIG4gPiAxOgoJCXAgPSBkaXZpc29yc1tuXQoJCWlmIHAgPT0gMToKCQkJcmVzdWx0LmFwcGVuZChuKQoJCQlyZXR1cm4gcmVzdWx0CgkJd2hpbGUgbiAlIHAgPT0gMDoKCQkJcmVzdWx0LmFwcGVuZChwKQoJCQluIC89IHAKCXJldHVybiByZXN1bHQKCQpwcmludCAxMDAwLCBmYWN0b3IoMTAwMCkKcHJpbnQgMjQsIGZhY3RvcigyNCkKcHJpbnQgMTcqMzEsIGZhY3RvcigxNyozMSkK
1000 [5, 5, 5, 2, 2, 2]
24 [3, 2, 2, 2]
527 [31, 17]