#!/usr/local/bin/python
# coding: iso-8859-1
# Copyright © 2008 by Amos Newcombe
# 
# This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
# 
# This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
# 
# You should have received a copy of the GNU General Public License along with this program.  If not, see <http://www.gnu.org/licenses/>.

'''Library routines to factor integers, and a command-line tool to call them.

If N = p1^k1 * p2^k2 * ... then factor(n) returns ((p1, k1), (p2, k2), ...). where the pn are the prime factors of N and 1 <= kn.
'''

def factorTD(n):
	'factor by trial division'
	ltp = []
	c = 0 # loop invariant: 2^c * n
	while n % 2 == 0: c += 1; n /= 2
	if c: ltp.append((2, c))
	i = 3
	while i*i <= n:
		c = 0 # loop invariant: i^c * n
		while n % i == 0: c += 1; n /= i
		if c: ltp.append((i, c))
		i += 2
	if 1 < n: ltp.append((n, 1))
	return ltp

def strfactors(ltp):
	return '*'.join([strfactor(tp) for tp in ltp])

def strfactor(tp):
	if tp[1] == 1: return '%d'    % tp[0]
	else         : return '%d^%d' % tp

if __name__ == '__main__':
	
	import sys
	from commander.commander import evaluator
	
	class factortest(evaluator):
		
		def function(self, sArg):
			return strfactors(factorTD(int(sArg)))
	
	factortest(sys.argv).main()