对一个 3000 位数字进行素因数分解，最大素数 <=104743（6 位）——这可能在几分钟内在“普通”计算机上完成吗？

Question

我有一个 3000 位长的数必须分解成它的素数。我知道没有大于104743的质因数。

这是否可能在几分钟内在“普通”计算机上完成，因为最高因子相对较低？

作为参考，我尝试了在这里找到的这段代码。

def factorize(n): 
    count = 0; 

    while ((n % 2 > 0) == False):  

        # equivalent to n = n / 2; 
        n >>= 1;  
        count += 1; 

    # if 2 divides it 
    if (count > 0): 
        print(2, count); 

    # check for all the possible 
    # numbers that can divide it 
    for i in range(3, int(math.sqrt(n)) + 1): 
        count = 0; 
        while (n % i == 0):  
            count += 1; 
            n = int(n / i); 
        if (count > 0): 
            print(i, count); 
        i += 2; 

    # if n at the end is a prime number. 
    if (n > 2): 
        print(n, 1); 

n = 5*7*11*13*17*19*23*29*31*37*41*43*47;
factorize(n); 

# This code is contributed by mits

此代码使用 59 秒来生成一个 18 位数字，其中 47 是最高因数（102481630431415235 是“测试号码”）。如果我停在第 47 个因素，它只用了 31 秒，但它仍然太长了，因为测试数量远低于我的需要。

Answer 1

因为你的素数比较小，我觉得如果你能先generate the list of primes然后用它们进行因式分解会更快。

这是一个示例代码：

import math

# Copied from 
def primes2(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1,int(n**0.5)//3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
        sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]

def factorize2(n, primes):
    factors = {}
    cur_num = n
    for p in primes:
        if p*p > cur_num:
            break
        while cur_num % p == 0:
            cur_num //= p
            factors[p] = factors.get(p, 0) + 1

    if cur_num >= 2:
        factors[cur_num] = factors.get(cur_num, 0) + 1
    return factors

# Precompute the primes
primes = primes2(110000)
n = 5*7*11*13*17*19*23*29*31*37*41*43*47

result = factorize2(n, primes)
print(result)

对于示例中的数字，此代码运行大约 50 毫秒（比您问题中的代码快得多）。

更新：

我试过使用以下代码输入 3000 位号码：

def generate_big_num(primes, th):
    import random
    num = 1
    while num < th:
        num *= random.choice(primes)
    return num

th = 10**3000
big_num = generate_big_num(primes, th)
print(big_num)
result = factorize2(big_num, primes)
print(result)

而且在我的笔记本电脑上只用了大约 60 毫秒。所以你的问题的答案是 Yes!

希望对您有所帮助！

对一个 3000 位数字进行素因数分解，最大素数 <=104743（6 位）——这可能在几分钟内在“普通”计算机上完成吗？

Prime factorize a 3000 digit number, with max prime <=104743 (6 digit) - is this possible to do on a “normal” computer in a few minutes?

python

primes

prime-factoring