빠른 소인수 분해

1.
def highest_prime_factor(n):

   if isprime(n):

      return n

   for x in xrange(2,int(n ** 0.5) + 1):

      if not n % x:

         return highest_prime_factor(n/x)

def isprime(n):

   for x in xrange(2,int(n ** 0.5) + 1):

      if not n % x:

         return False

   return True

if  __name__ == "__main__":

   import time

   start = time.time()

   print highest_prime_factor(1238162376372637826)

   print time.time() - start

2.

def factor(n):

        if n == 1: return [1]

        i = 2

        limit = n**0.5

        while i <= limit:

                if n % i == 0:

                        ret = factor(n/i)

                        ret.append(i)

                        return ret

                i += 1

        return [n]

2-1.

def factor(n):

    yield 1

    i = 2

    limit = n**0.5

    while i <= limit:

        if n % i == 0:

            yield i

            n = n / i

            limit = n**0.5

        else:

            i += 1

    if n > 1:

        yield n

3.

import random

from Queue import Queue

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 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 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=[]

    Q_1.put(n)

    while(not Q_1.empty()):

        l=Q_1.get()

        if(rabin_miller(l)):

            Q_2.append(l)

            continue

        d=pollard(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=input();

        L=factor(n)

        L.sort()

        i=0

        while(i<len(L)):

            cnt=L.count(L[i])

            print L[i],'^',cnt

            i+=cnt 





Update : factor2()가 가장 빠르다.

def factor1(n):

    if n == 1: return [1]

    i = 2

    limit = n**0.5

    while i <= limit:

        if n % i == 0:

            ret = factor1(n/i)

            ret.append(i)

            return ret

        i += 1

    return [n]

def factor2(n):

##    yield 1

    i = 2

    limit = n**0.5

    while i <= limit:

        if n % i == 0:

            yield i

            n = n / i

            limit = n**0.5

        else:

            i += 1

    if n > 1:

        yield n

if  __name__ == "__main__":

    import time

    print 'factor1'

    start = time.time()

    print factor1(200000000000000000000000000009)

    print time.time() - start

    print 'factor2'

    start = time.time()

    print [i for i in factor2(200000000000000000000000000009)]

    print time.time() - start

출처 : http://stackoverflow.com/questions/2403578/fastest-calculation-of-largest-prime-factor-of-512-bit-number-in-python