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]
--
http://mail.python.org/mailman/listinfo/python-list
