Problem Regarding Queue

mukesh tiwari mukeshtiwari.iiitm at gmail.com
Tue Feb 9 23:06:56 CET 2010


Could some one please tell what is wrong with this code. I am trying
to use Queue in this program but i am getting error
Traceback (most recent call last):
  File "/home/user/NetBeansProjects/NewPythonProject2/src/
Pollard_rho.py", line 80, in <module>
    factor(n)
  File "/home/user/NetBeansProjects/NewPythonProject2/src/
Pollard_rho.py", line 59, in factor
    Q_1=Queue()
NameError: global name 'Queue' is not defined.
As i am new to python so kindly pardon me if  i sound stupid.
Here is the code
# 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
import sys
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

def rabin_miller(p):
	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(10):
		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 pollard(n):
        if(n%2==0):
            return 2;
        x=random.randrange(2,1000000)
        c=random.randrange(2,1000000)
        y=x
        d=1
        while(d==1):
            x=(x*x+c)%n
            y=(y*y+c)%n
            y=(y*y+c)%n
            d=gcd(x-y,n)
            if(d==n):
                break;
        return d;
def factor(n):
    #if(rabin_miller(n)):
     #   print n
      #  return
    #d=pollard(n)
    #if(d!=n):
     #   factor(d)
      #  factor(n/d)
    #else:
     #   factor(n)

    Q_1=Queue()
    Q_2=Queue()
    Q_1.put(n)
    while(not Q_1.empty()):
        l=Q_1.get()
        if(rabin_miller(l)):
            Q_2.put(l)
            continue
        d=pollard(l)
        if(d==l):Q_1.put(l)
        else:
            Q_1.put(d)
            Q_1.put(l/d)
    while(not Q_2.empty()):
        print Q_2.get()



if __name__ == "__main__":
    while(True):
        n=input();
        factor(n)



More information about the Python-list mailing list