Почему я не могу найти простые делители числа 2^32 - 1?

Question

Почему я не могу найти простые делители числа 2^32-1? Что нужно сделать, чтобы он смог работать с большими числами?

    def simple_num(M):
            b = []
            for i in range(M - 1, 1, -1):
                is_simple = 0
                if (M % i == 0):
                    for j in range(i - 1, 1, -1):
                        if (i % j == 0):
                            is_simple = is_simple + 1 # Увеличиваем, если находим делитель
                    if (is_simple == 0): # Если делителей не было найдено, выводим
                        b.append(i)
            print(b)
            return b

n = simple_num(pow(2, 32) - 1)

Answer 1

какой бы я предложил бы алгоритм:

согласно основной теореме арифметики число представляет собой уникальное произведение простых множителей, поэтому чтобы найти все простые множители я бы делал так:

шел бы от 2 до N ища делитель
если делитель найден - делил бы число M до тех пор, пока оно делится

повторял бы шаги 1) и 2) начиная с последнего найденного простого делителя + 1

 def simple_num(M):
     res = []
     prime = 1
     while M > 1:
         # ищем простой делитель
         for i in range(prime + 1, M + 1):
             if M % i == 0:
                 prime = i
                 res.append(prime)

                 # уменьшаем число пока возможно
                 while M % i == 0:
                     M = M // i

                 # прервать цикл
                 break

             # если множителя найдено не было - выйти
             if i == M:
                 return res

     return res

 M = int(input())
 res = simple_num(M)

 print(*res)

Касательно больших чисел: вот что выдает программа

> 5082789810833999408925496308481218199348328424960000

2 3 5 7 11 19 23 29 47 53 59 107 421 659 829 967 2671 3593 15401

Answer 2

Решил написать в новом комментарии, чтоб кода не добавлять много в старый

Поскольку нужны только ПРОСТЫЕ делители, то не требуется рассматривать все числа в диапазоне 2..n, достаточно рассматривать числа в диапазоне 2..sqrt(n), что сводит сложность задачи с O(n) до O(sqrt(n)) и значительно ее ускоряет:

def simple_num(M):
    res = []
    prime = 1
    while M > 1:
        # ищем простой делитель
        limit = int(M**0.5)
        
        for i in range(prime + 1, limit + 1):
            if M % i == 0:
                prime = i
                res.append(prime)

                # уменьшаем число пока возможно
                while M % i == 0:
                    M = M // i

                # прервать цикл
                break

            # если множителя найдено не было - выйти
            if i >= limit:
                res.append(M)
                return res

    return res


M = 2**31 - 1 #int(input())
res = simple_num(M)

print(*res)

БЛОГ НА HUSL

Почему я не могу найти простые делители числа 2^32 - 1?

Ответы (2 шт):