Python Optimization

[mukesh tiwari]

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]