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

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%). Если чисел много, то уже появится смысл какие-то предподсчеты делать и решето из моего ответа тут будет самым эффективным методом.

[Дмитрий Наконечный]

Wataru, стало интересно, о каких микрооптимизациях Вы говорите. Расскажете? Буду очень признателен :)

[Wataru]

PythonDemon, делитель 2 обработать битовыми операциями. А дальше начинать с 3 и делать +=2. Не считать i*i каждый раз, а один раз подсчитать sqrt(n). Вместо if-else использовать вложенный while. Возможно это будет быстрее из-за более короткого и развернутого цикла.

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

[Дмитрий Наконечный]

Wataru, да, насчет С++ сразу понял :)
Спасибо, что подсказали насчет остальных оптимизаций!

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]

Answer 4

[ArseniyRybasov]

Есть 2 приходящих на ум быстрых способов поиска делителей числа. Это поиск до корня числа и разложение числа на простые множители и перебор всех их комбинаций.
Первый способ программа на Python ищет делители числа 72576 * 10 ^ 12 (2600 делителей) за 22,742 секунды. Второй кажется быстрее, но из-за самого принципа поиска код получается длинным и сложным и программа будет искать делители вечность xD

Но самый быстрый способ - это тот, который я придумал). Он выполняется так:
1. Раскладывает число на простые множители
2. Идёт по списку простых множителей (i) и списку всех известных делителей числа (j):
2.1. Если (простой множитель с индексом i) * (известный делитель с индексом j) не встречается в списке известных делителей числа, то в список это значение не добавляется (чтобы каждый раз цикл не проходился по повторяющимся значениям)
2.2. Если простой множитель с индексом i отсутствует, то он добавляется
3. Добавляет в конце списка делителей числа единицу
4. Возвращает отсортированный список

Моя реализация:

def divisors(n):
    divs = []
    prdivs = []
    nownum = n
    isPrime = False

    while isPrime == False:
        isPrime = True
        for i in range(2, int(nownum ** 0.5) + 1):
            if nownum % i == 0:
                prdivs.append(i)
                isPrime = False
                nownum //= i
                break

    prdivs.append(nownum)

    for i in range(len(prdivs)):
        for j in range(len(divs)):
            if divs[j] * prdivs[i] not in divs:
                divs.append(divs[j] * prdivs[i])

        if prdivs[i] not in divs:
            divs.append(prdivs[i])

    divs.append(1)
    return sorted(divs)

Он ищет делители числа 72576 * 10 ^ 12 за 0,055 секунд, а у числа 72576 * 10 ^ 50 (29580 делителей) за 17,489 секунд!

Comments

[Дмитрий Наконечный]

Мне кажется, Вы новичок в спортивном программировании, т.к. придаете своему алгоритму слишком большое значение. Он работает быстро лишь для частных случаев, где простые делители числа малы. Попробуйте свой алгоритм на простом числе. Попробуйте на произведении двух простых чисел порядка 10^25. Видите разницу? Естественно, можно такой алгоритм запустить и на 72576 * 10 ^ 50 запустить, потому что он быстро найдет делители по типу двойки и пятерки, а после деления на них число для дальнейшего поиска вообще крохотное.
P.S. Очень редко когда очевидный алгоритм, лежащий на поверхности, оказывается во много раз более оптимальным. Здесь два варианта - либо он не решает задачу, либо решает для каких-то специфических случаев :)
Но вообще идея деления на простой делитель после его нахождения очень хороша, хотя и не нова. Удачи и успехов в дальнейшем изучении, у Вас хорошо получается ;)