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?

I have a 3000 digits long number must be factored into its prime numbers. I know that there are no prime factors larger than 104743.

Is this possible to do on a “normal” computer in a few minutes since the highest factor is relatively low?

As a reference, I tried this code I found here.

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

This code use 59 seconds to factories a 18-digit number with 47 being the highest factor (102481630431415235 was the “test number”). If I stop at the 47th factor it use only 31 seconds, but it is still way too long with the test number being far lower than my need.

Solution

Since your primes are relatively small, I think it would be faster if you can generate the list of primes first and use them for factorization.

Here is an example code:

import math

# Copied from https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n/3035188#3035188
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)

For the number in the example this code run around 50ms (which much faster than the code in your question).

UPDATE:

I have tried on 3000 digits number with the following codes:

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)

And it only took around 60ms on my laptop. So the answer for your question is Yes!

Hope this helps!