M

#### mukesh tiwari

c/c++.Could some one please help me to improve the run time for this

python program as i don't have idea how to optimized this code.This

code also seems to be more unpythonic so how to make it look like more

pythonic . I am trying for this problem(https://www.spoj.pl/problems/

FACT1/).

Thank you

# To change this template, choose Tools | Templates

# and open the template in the editor.

__author__="Mukesh Tiwari"

__date__ ="$Feb 10, 2010 1:35:26 AM$"

import random

from Queue import Queue

def gcd(a,b):

while b:

a,b=b,a%b

return a

def rabin_miller(p,t=1):

if(p<2):

return False

if(p!=2 and p%2==0):

return False

s=p-1

while(s%2==0):

s>>=1

for i in xrange(t):

a=random.randrange(p-1)+1

temp=s

mod=pow(a,temp,p)

while(temp!=p-1 and mod!=1 and mod!=p-1):

mod=(mod*mod)%p

temp=temp*2

if(mod!=p-1 and temp%2==0):

return False

return True

def brent(n):

if(n%2==0):

return 2;

x,c,m=random.randrange(0,n),random.randrange(1,n),random.randrange(1,n)

y,r,q=x,1,1

g,ys=0,0

while(True):

x=y

for i in range(r):

y,k=(y*y+c)%n,0

while(True):

ys=y

for i in range(min(m,r-k)):

y,q=(y*y+c)%n,q*abs(x-y)%n

g,k=gcd(q,n),k+m

if(k>= r or g>1):break

r=2*r

if(g>1):break

if(g==n):

while(True):

ys,g=(x*x+c)%n,gcd(abs(x-ys),n)

if(g>1):break

return g

def factor(n):

Q_1,Q_2=Queue(),[]

Q_1.put(n)

while(not Q_1.empty()):

l=Q_1.get()

if(rabin_miller(l)):

Q_2.append(l)

continue

d=brent(l)

if(d==l):Q_1.put(l)

else:

Q_1.put(d)

Q_1.put(l/d)

return Q_2

if __name__ == "__main__":

while(True):

n=int(raw_input())

if(n==0):break

L=factor(n)

L.sort()

#print L

i=0

s=""

while(i<len(L)):

cnt=L.count(L

*)*

#print "%d^%d"%(L

#print "%d^%d"%(L

*,cnt)*

s+=str(Ls+=str(L

*)+"^"+str(cnt)+" "*

i+=cnt

print s[:-1]i+=cnt

print s[:-1]