# Copyright (C) 2004 Marc O. Sandlus
# Homepage: http://www.matheraum.de/werkzeuge

# 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 2 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, write to the Free Software
# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

import math

werkzeugid = "primfaktorzerlegung"
author = "Marc O. Sandlus"
licence = "GNU General Public License"
username = "Marc"


def primfaktorenzerlegung( dez, startp=2 ):
	dez = long( dez )
	
	if dez in primfaktoren:
		#return "%s" % dez
		return [ dez ]
	
	if startp < primfaktoren[-1]:
		for p in primfaktoren:
			quotient, rest = divmod( dez, p )
		
			if not rest:
				#return "%s&middot;%s" % ( p, primfaktorenzerlegung( quotient, startp=p ) )
				return [ p ] + primfaktorenzerlegung( quotient, startp=p )
	
	maxprimfaktor = long( math.sqrt( dez ) )

	if maxprimfaktor > primfaktoren[-1]:
		for p in xrange( max( startp, primfaktoren[-1]+2 ), maxprimfaktor, 2 ):
			quotient, rest = divmod( dez, p )

			if not rest:
				#return "%s&middot;%s" % ( p, primfaktorenzerlegung( quotient, startp=p ) )
				primfaktoren.append( p )
				return [ p ] + primfaktorenzerlegung( quotient, startp=p )
	
	return [ dez ]

primfaktoren = [ 2 ]
for n in range( 3, 1000 ):
	if primfaktorenzerlegung( n ) == [ n ]:
		primfaktoren.append( n )

#print primfaktoren

def webform( reqform, results=0 ):
	form = { 'input':'',
			}
	form.update( reqform )
	
	res = { 'title': 'Primfaktorzerlegung' }
	
	s = ""
	s += '<p>Zerlegt die einzugebende natürliche Zahl in ihre Primfaktoren.</p>'
	
	s += '<form action="werkzeuge" method="GET">\n'
	s += '<input type="hidden" name="werkzeug" value="primfaktorzerlegung">\n'
	
	s += '<table border=0>\n'
	s += '<tr><th>zu zerlegende Zahl</th> <th>&nbsp;</th> </tr>\n'
	s += '<tr><td>'
	s += '<input name="input" value="%(input)s" size="40" maxlength="400">\n' % form
	s += '</td><td>'
	s += '<input type="submit" value=" berechne! ">\n'
	s += '</td></tr>'
	s += '<tr><td>&nbsp;</td><td>(max. 1.000.000.000.000)</td><td>&nbsp;</td></tr>\n'
	s += '</table>\n'
	
	s += '</form>\n'
	
	if results and form[ 'input' ].strip():
		error = dezimalzahl = None
		try:
			dezimalzahl = abs( long( form[ 'input' ] ) )
		except ValueError:
			error = "Eingabe konnte nicht als Zahl interpretiert werden."
		except TypeError:
			error = "Eingabe konnte nicht als Zahl interpretiert werden."
		
		if not error:
			if dezimalzahl > 1000000000000:
				error = "Zahl zu groß"
			
		if not error:
			pfz = primfaktorenzerlegung( dezimalzahl )
			if len( pfz ) == 1:
				s += '<p><b>Ergebnis</b>: %s ist prim.</p>\n' % dezimalzahl
			else:
				s += '<p><b>Ergebnis</b>: %s</p>\n' % reduce( lambda s,t: "%s&middot;%s" % ( s, t ), pfz[1:], pfz[0] )
		else:
			s += '<p><b>Fehler</b>: %s</p>\n' % error
	
	res.update( { 'html':s } )
	return res

def kgV( a, b ):
	#print a,b
	res = (a*b) / ggT( a,b )
	#print "kgV(%s,%s)=%s" % ( a,b,res )
	return res

def ggT( a, b ):
	#print a,b
	p1 = primfaktorenzerlegung( a )
	p2 = primfaktorenzerlegung( b )

	res = 1
	for p in p1:
		if p in p2:
			res *= p
			p2.remove( p )
			
	#print "ggT(%s,%s)=%s" % ( a,b,res )
	return res

if __name__ == '__main__':
	print primfaktorenzerlegung( 3552664958674928 )	
	primzahlen = []
	for n in xrange( 591118393, 1000000000 ):
		if len( primfaktorenzerlegung( n ) ) == 1:
			print "%s" % n
			primzahlen.append( n )
## vim:ts=4