если вы не хотите изобретать велосипед, используйте библиотека sympy

pip install sympy

использование функции sympy.ntheory.factorint

>>> from sympy.ntheory import factorint
>>> factorint(10**20+1)
{73: 1, 5964848081: 1, 1676321: 1, 137: 1}

вы можете разложить некоторые очень большие числа:

>>> factorint(10**100+1)
{401: 1, 5964848081: 1, 1676321: 1, 1601: 1, 1201: 1, 137: 1, 73: 1, 129694419029057750551385771184564274499075700947656757821537291527196801: 1}

нет необходимости расчета smallprimes С помощью primesbelow используйте smallprimeset для этого.

smallprimes = (2,) + tuple(n for n in xrange(3,1000,2) if n in smallprimeset)

разделить primefactors на две функции для обработки smallprimes и pollard_brent, это может сэкономить пару итераций, так как все степени smallprimes будут разделены от n.

def primefactors(n, sort=False):
    factors = []

    limit = int(n ** .5) + 1
    for checker in smallprimes:
        print smallprimes[-1]
        if checker > limit: break
        while n % checker == 0:
            factors.append(checker)
            n //= checker


    if n < 2: return factors
    else : 
        factors.extend(bigfactors(n,sort))
        return factors

def bigfactors(n, sort = False):
    factors = []
    while n > 1:
        if isprime(n):
            factors.append(n)
            break
        factor = pollard_brent(n) 
        factors.extend(bigfactors(factor,sort)) # recurse to factor the not necessarily prime factor returned by pollard-brent
        n //= factor

    if sort: factors.sort()    
    return factors

рассматривая проверенные результаты Pomerance, Selfridge и Wagstaff и Jaeschke, вы можете уменьшить повторения в isprime который использует Миллер-Рабин тест на первичность. От Wiki.

• если n
• если n
• если n
• если n
• если n
• если n

изменить 1: исправлен обратный звонок if-else чтобы добавить bigfactors к факторам в primefactors.

даже на текущем, есть несколько пятен, чтобы быть замеченным.

1. не checker*checker каждый цикл, используйте s=ceil(sqrt(num)) и checher < s
2. Чечер должен плюс 2 каждый раз, игнорировать все четные числа, кроме 2
3. использовать divmod вместо % и //

вы, вероятно, должны сделать некоторые простые обнаружения, которые вы могли бы посмотреть здесь, быстрый алгоритм поиска простых чисел?

вы должны прочитать весь этот блог, хотя, есть несколько алгоритмов, которые он перечисляет для тестирования примитивности.

есть библиотека python с коллекцией тестов на примитивность (включая неправильные для того, что не нужно делать). Это называется pyprimes. Решил, что это стоит упомянуть для целей потомства. Я не думаю, что это включает в себя алгоритмы, которые вы упомянули.

я просто столкнулся с ошибкой в этом коде при факторинге числа 2**1427 * 31.

  File "buckets.py", line 48, in prettyprime
    factors = primefactors.primefactors(n, sort=True)
  File "/private/tmp/primefactors.py", line 83, in primefactors
    limit = int(n ** .5) + 1
OverflowError: long int too large to convert to float

этот фрагмент кода:

limit = int(n ** .5) + 1
for checker in smallprimes:
    if checker > limit: break
    while n % checker == 0:
        factors.append(checker)
        n //= checker
        limit = int(n ** .5) + 1
        if checker > limit: break

следует переписать в

for checker in smallprimes:
    while n % checker == 0:
        factors.append(checker)
        n //= checker
    if checker > n: break

который, вероятно, будет работать быстрее на реалистичных входах в любом случае. Квадратный корень медленный-в основном эквивалент многих умножений -,smallprimes всего несколько десятков членов, и таким образом мы убираем расчета n ** .5 от плотной внутренней петли, которая определенно полезна когда факторинг чисел, как 2**1427. Там просто нет причин, чтобы вычислить sqrt(2**1427),sqrt(2**1426),sqrt(2**1425) и т. д. так далее., когда все, о чем мы заботимся, это "превышает ли [квадрат] checker n".

переписанный код не вызывает исключений при представлении больших чисел,и это примерно в два раза быстрее по timeit (на входах выборки 2 и 2**718 * 31).

также обратите внимание, что isprime(2) возвращает неправильный результат, но это нормально, пока как мы на это не рассчитываем. IMHO вы должны переписать вступление этой функции как

if n <= 3:
    return n >= 2
...

вы можете факторизовать до предела, а затем использовать brent для получения более высоких коэффициентов

from fractions import gcd
from random import randint

def brent(N):
   if N%2==0: return 2
   y,c,m = randint(1, N-1),randint(1, N-1),randint(1, N-1)
   g,r,q = 1,1,1
   while g==1:             
       x = y
       for i in range(r):
          y = ((y*y)%N+c)%N
       k = 0
       while (k<r and g==1):
          ys = y
          for i in range(min(m,r-k)):
             y = ((y*y)%N+c)%N
             q = q*(abs(x-y))%N
          g = gcd(q,N)
          k = k + m
       r = r*2
   if g==N:
       while True:
          ys = ((ys*ys)%N+c)%N
          g = gcd(abs(x-ys),N)
          if g>1:  break
   return g

def factorize(n1):
    if n1==0: return []
    if n1==1: return [1]
    n=n1
    b=[]
    p=0
    mx=1000000
    while n % 2 ==0 : b.append(2);n//=2
    while n % 3 ==0 : b.append(3);n//=3
    i=5
    inc=2
    while i <=mx:
       while n % i ==0 : b.append(i); n//=i
       i+=inc
       inc=6-inc
    while n>mx:
      p1=n
      while p1!=p:
          p=p1
          p1=brent(p)
      b.append(p1);n//=p1 
    if n!=1:b.append(n)   
    return sorted(b)

from functools import reduce
#n= 2**1427 * 31 #
n= 67898771  * 492574361 * 10000223 *305175781* 722222227*880949 *908909
li=factorize(n)
print (li)
print (n - reduce(lambda x,y :x*y ,li))