Python Optimization

[Mark Lawrence]

mukesh tiwari wrote:
> Hello everyone. I am new to python and previously i did programming in
> 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[i])
>             #print "%d^%d"%(L[i],cnt)
>             s+=str(L[i])+"^"+str(cnt)+" "
>             i+=cnt
>         print s[:-1]

A good starting point is 
http://wiki.python.org/moin/PythonSpeed/PerformanceTips

HTH.

Mark Lawrence