Эффективный код Python для печати произведения делителей числа

Question

Я пытаюсь решить проблему, связанную с печатью произведения всех делителей заданного числа. Число тестовых примеров - это число 1 <= t <= 300000, а само число может варьироваться от 1 <= n <= 500000 </p>

Я написал следующий код, но он всегда превышает 2 секунды. Есть ли способы ускорить код?

from math import sqrt

def divisorsProduct(n):
    ProductOfDivisors=1

    for i in range(2,int(round(sqrt(n)))+1):
        if n%i==0: 
            ProductOfDivisors*=i

            if n/i != i:
                ProductOfDivisors*=(n/i)    

    if ProductOfDivisors <= 9999:
        print ProductOfDivisors
    else:
        result = str(ProductOfDivisors)
        print result[len(result)-4:] 

T = int(raw_input())

for i in range(1,T+1):
    num = int(raw_input())
    divisorsProduct(num)

Спасибо.

Answer 1

Вы должны уточнить, что вы подразумеваете под «произведением делителей». Код, размещенный в вопросе, пока не работает ни для какого определения. Это звучит как домашнее задание. Если это так, то, возможно, ваш инструктор ожидал, что вы будете думать за пределами кода, чтобы достичь временных целей.

Если вы имеете в виду произведение уникальных простых делителей, например, 72 дает 2 * 3 = 6, тогда вам нужно иметь список простых чисел. Просто пролистайте список до квадратного корня из числа, умножая имеющиеся простые числа на результат. Их не так много, так что вы можете даже жестко запрограммировать их в своей программе.

Если вы имеете в виду произведение всех делителей, простых или нет, то полезно подумать о том, что такое делители. Вы можете получить серьезное увеличение скорости по сравнению с методом грубой силы, предложенным в других ваших ответах. Я подозреваю, что это то, что задумал ваш инструктор.

Если делители упорядочены в списке, то они встречаются парами, которые умножаются на n - 1 и n, 2 и n / 2 и т. Д. - за исключением случая, когда n - идеальный квадрат, где квадратный корень - это делитель, который не связан ни с одним другим.

Таким образом, результатом будет n в степени, равной половине числа делителей (независимо от того, является ли n квадратом).

Чтобы вычислить это, найдите простую факторизацию, используя ваш список простых чисел. То есть найдите степень 2, которая делит n, затем степень 3 и т. Д. Для этого уберите все 2, затем 3 и т. Д.

Число, из которого вы убираете множители, будет уменьшаться, поэтому вы можете выполнить тест с квадратным корнем для промежуточных чисел меньшего размера, чтобы узнать, нужно ли вам продолжить список простых чисел. Чтобы получить некоторую скорость, протестируйте p * p <= m, а не p <= sqrt (m) </p>

Если у вас есть основная факторизация, легко найти количество делителей. Например, предположим, что факторизация равна 2 ^ i * 3 ^ j * 7 ^ k. Тогда, поскольку каждый делитель использует одни и те же простые множители с показателями, меньшими или равными показателям в n, включая возможность 0, число делителей равно (i + 1) (j + 1) (k + 1).

Например, 72 = 2 ^ 3 * 3 ^ 2, поэтому число делителей равно 4 * 3 = 12, а их произведение равно 72 ^ 6 = 139,314,069,504.

При использовании математики алгоритм может стать намного лучше, чем O (n). Но трудно заранее оценить выигрыш в скорости из-за относительно небольшого размера n на входе.

Answer 2

Хорошо, я думаю, что это близко к оптимальному алгоритму. Он производит product_of_divisors для каждого числа в диапазоне (500000).

import math

def number_of_divisors(maxval=500001):
    """ Example: the number of divisors of 12 is 6:  1, 2, 3, 4, 6, 12.
        Given a prime factoring of n, the number of divisors of n is the
        product of each factor's multiplicity plus one (mpo in my variables).

        This function works like the Sieve of Eratosthenes, but marks each
        composite n with the multiplicity (plus one) of each prime factor. """
    numdivs = [1] * maxval   # multiplicative identity
    currmpo = [0] * maxval

    # standard logic for 2 < p < sqrt(maxval)
    for p in range(2, int(math.sqrt(maxval))):
        if numdivs[p] == 1:   # if p is prime
            for exp in range(2,50): # assume maxval < 2^50
                pexp = p ** exp
                if pexp > maxval:
                    break
                exppo = exp + 1
                for comp in range(pexp, maxval, pexp):
                    currmpo[comp] = exppo
            for comp in range(p, maxval, p):
                thismpo = currmpo[comp] or 2
                numdivs[comp] *= thismpo
                currmpo[comp] = 0  # reset currmpo array in place

    # abbreviated logic for p > sqrt(maxval)
    for p in range(int(math.sqrt(maxval)), maxval):
        if numdivs[p] == 1:   # if p is prime
            for comp in range(p, maxval, p):
                numdivs[comp] *= 2

    return numdivs

# this initialization times at 7s on my machine
NUMDIV = number_of_divisors()

def product_of_divisors(n):
    if NUMDIV[n] % 2 == 0:
        # each pair of divisors has product equal to n, for example
        # 1*12 * 2*6 * 3*4  =  12**3
        return n ** (NUMDIV[n] / 2)
    else:
        # perfect squares have their square root as an unmatched divisor
        return n ** (NUMDIV[n] / 2) * int(math.sqrt(n))

# this loop times at 13s on my machine
for n in range(500000):
    a = product_of_divisors(n)

На моей очень медленной машине требуется 7 секунд, чтобы вычислить число делителей для каждого числа, затем 13 секунд, чтобы вычислить произведение делителей для каждого. Конечно, его можно ускорить, переведя его на C. (@ someone с быстрой машиной: сколько времени это займет на вашей машине?)

Answer 3

Вы можете исключить оператор if в цикле, выполнив цикл только до меньшего, чем квадратный корень, и проверить целочисленность квадратного корня вне цикла.

Это довольно странный вопрос, который вы задаете. Я с трудом представляю себе его применение, кроме того, что оно может быть заданием в курсе. Моя первая мысль состояла в том, чтобы предварительно вычислить список простых чисел и проверить только их, но я предполагаю, что вы вполне сознательно подсчитываете непростые факторы? То есть, если число имеет факторы 2 и 3, вы также учитываете 6.

Если вы используете таблицу предварительно вычисленных простых чисел, вам придется впоследствии впоследствии включать в свой результат все возможные комбинации простых чисел, которые становятся более сложными.

C действительно отличный язык для такого рода вещей, потому что даже неоптимальные алгоритмы работают очень быстро.