优化半素数分解算法

Question

我下面的方法超级粗鲁，超级慢。关于优化建议的任何提示。我知道对于两个不同素数的半素数，数字小于或等于半素数的一半。但我不确定如何更有效地检查大数的素数列表。对于 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 位数字。

优化半素数分解算法

Optimizing Semi-prime Factoring Algo

python

optimization

sieve-of-eratosthenes

factorization