セミプライムファクタリングアルゴリズムを最適化

Question

私の以下の方法は、スーパークーパーとスーパークーパーです。最適化に関する提案に関するヒント。私は2つの異なる素数のセミプライムについて知っていますが、その数はセミプライムの半分以下です。しかし、素数のリストを大量に効率的にチェックする方法についてはわかりません。 nが13桁の場合は、鉱山が崩壊すると大きくなります。

import math 
def eratosthenes(n): 
    multiples = set() 
    primes = set() 
    for i in range(2, n+1): 
     if i not in multiples: 
      if i <= math.ceil(math.sqrt(n)+10): 
       primes.add(i) 
        for j in range(i*i, n+1, i): 
         multiples.add(j) 
    result = [] 
    for p in primes: 
     while n % p == 0: # while p divide n... 
      result.append(p) 
      n = n // p 
     if n <= 1: 
      break 

Answer 1

大きな素数のためには、Pollard's rho algorithm

from fractions import gcd 

def pollardfactor(n): 
    a=2 
    b=2 
    d=1 
    for c in [1,-1,2,3,5,7,-3,-5,-7]: 
     while True: 
      a=(a*a+c)%n 
      b=(b*b+c)%n 
      b=(b*b+c)%n 
      d=gcd(abs(a-b),n) 
      if 1 < d < n: 
       return(d) 
      elif d==n : 
       break 
    return -1 

print(pollardfactor(5983391455009)) 

これは、合理的な時間内に20桁の番号のために働くべきで実装するのは簡単で試すことができます。