Простое разложение на множители 3000 ди git с максимальным простым <= 104743 (6 ди git) - возможно ли это сделать на «обычном» компьютере за несколько минут?

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-значного числа git, где 47 является наивысшим фактором (102481630431415235 был «номером испытания»). Если я остановлюсь на 47-м факторе, он будет использовать только 31 секунду, но он все равно будет слишком длинным, так как число тестов будет намного меньше, чем нужно.

Answer 1

Поскольку ваши простые числа относительно малы, я думаю, что было бы быстрее, если бы вы сначала сгенерировали список простых чисел и использовали их для факторизации.

Вот пример кода:

Для числа в примере этот код работает около 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 мс на моем ноутбуке. Итак, ответ на ваш вопрос: Да !

Надеюсь, это поможет!