Более быстрый способ нахождения всех делителей числа?

Question

[Idwln]

Хочу узнать, какой наиболее быстрый способ нахождения всех делителей числа есть?( в среднем случае )
Пользовался всегда данным(указанным ниже) куском кода, но решал простые задачи. Когда дело пришло к большим цифрам, понял, что он не самый эффективный.
Код:

import collections
import itertools


def get_prime_divisors(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            n /= i
            yield i
        else:
            i += 1

    if n > 1:
        yield n


def calc_product(iterable):
    acc = 1
    for i in iterable:
        acc *= i
    return acc


def get_all_divisors(n):
    primes = get_prime_divisors(n)

    primes_counted = collections.Counter(primes)

    divisors_exponentiated = [
        [div ** i for i in range(count + 1)]
        for div, count in primes_counted.items()
    ]

    for prime_exp_combination in itertools.product(*divisors_exponentiated):
        yield calc_product(prime_exp_combination)

P.s: Сам код взял из интернета, ибо в первый раз не было времени придумывать свой велосипед.

Comments

[Алан Гибизов]

Без попытки решения выглядит как задание, а не вопрос. Рекомендую привести свою попытку, пусть неудачную, нерабочую. Тогда будет предмет для обсуждения. Сейчас вопрос кандидат на удаление.

[Алан Гибизов]

Также надо привести название вопроса в соответствие п.3.4 Регламента.

[Idwln]

Алан Гибизов, В следующий раз буду уточнять, спасибо

[Алан Гибизов]

Idwln, вы уже не первый раз вопрос задаёте, а с правилами не ознакомились и не выполняете. Это не рекомендация, а указание. Вопрос НЕОБХОДИМО исправить и дополнить.

Answer 1

[mayton2019]

Суть вопроса - алгоритм факторизации.

Чтобы ускорить факторизацию есть много путей. Во первых - отказаться от языка Python в пользу C++ или Rust.

Во вторых - запоминать найденные primes и использовать их для следующего шага. Грубо говоря факторизация требует эффективного генератора primes. А он в свою очередь... Саморекурсивен. Требует такого-же генератора меньшей мощности.

И step надо делать не по 1 элементу а по нечётным начиная с 3.

Есть ещё алгоритм Эратосфена. Обрати внимание.

И есть очень глобальная задача, такая как доказательство простоты. Для нее есть целый список алгоритмов. Они сложные и интересные. Часть из них - вероятностные. Используются в критпографии.

Answer 2

[Wataru]

Это самый быстрый способ факторизации одного числа. Если не хватает, то может в задаче можно факторизовать все числа сразу. Каким нибудь решетом можно найти минимальный делитель для всех чисел до n за O(n). Дальше каждое число раскладывается на множители моментально.

Comments

[Akina]

Это самый быстрый способ факторизации одного числа.

Ну самый быстрый - это всё же использование предрасчётного списка простых чисел (который обычно читается из внешнего файла). Благо такие списки существуют, в т.ч. в достаточно большом диапазоне (правда, места жрут не по-детски, но это всё равно лучше, чем то же, но считать).

[Wataru]

Akina, по идее, надо считать и время рассчета этих простых чисел. Но даже если нет, то время их загрузки с диска будет все равно дольше метода в вопросе.

Это имеет смысл, когда вам надо много чисел раскладывать на множители. Тогда расчет/загрузка простых размажется по всем запросам.

[mayton2019]

Не нужны вам никакие списки. До мильена за несколько секунд вы сгенерируете на лету сами. И то для большинства составных чисел делители будут найдеты в первой сотне простых.

[Wataru]

mayton2019,

До мильена за несколько секунд вы сгенерируете на лету сами.

Но разложение любого числа до миллиона на множители алгоритмом из вопроса - это будет доли секунды. Поэтому тратить в сотни раз больше времени на расчет простых чисел, чтобы потом чуть быстрее разложить само число, нет никакого смысла. Даже если ограничиться только певрой сотней простых.

Поэтому я еще раз повторю: для разложения одного числа - быстрее метода нет (если не считать всякие микрооптимизации кода из вопроса для выигрыша 10-20%). Если чисел много, то уже появится смысл какие-то предподсчеты делать и решето из моего ответа тут будет самым эффективным методом.

Answer 3

[sheerluck]

Я нахожу все делители числа в SageMath (https://www.sagemath.org):

sage: 256893450689.divisors()
[1, 19, 13520707931, 256893450689]
sage: 252323674611367475532285533.divisors()
[1, 110933, 2267937467, 1002919711403, 251589107026711, 111256892345068999, 2274559189883690836201, 252323674611367475532285533]