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 секунд!