Понимание функции факторизации

Question

Обратите внимание, что этот вопрос содержит некоторые спойлеры.

A решение проблемы # 12 гласит, что

"Количество делителей (включая 1 и числосам) может быть вычислен с использованием одного элемента из простых (и степенных) делителей. "

Код (python), который делает это, имеет вид num_factors = lambda x: mul((exp+1) for (base, exp) in factorize(x)) (где mul() равен reduce(operator.mul, ...).)

В нем не указано, как определяется factorize, и мне трудно понять, как это работает.Как это говорит вам количество факторов числа?

Answer 1

Основная идея заключается в том, что если у вас есть число, разложенное на следующую форму, которая фактически является стандартной формой:

let p be a prime and e be the exponent of the prime:

N = p1^e1 * p2^e2 *....* pk^ek

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

e1 * e2 * e3 *...* ek

Но вы должны заметить, что если показатель в стандартной форме одного из простых факторов равен нулю, то результатом также будет делитель. Это означает, что мы должны добавить один к каждому показателю степени, чтобы удостовериться, что мы включили ith p в степень нуля. Вот пример, использующий число 12 - то же самое, что и номер вопроса: D

Let N = 12
Then, the prime factors are:
2^2 * 3^1
The divisors are the multiplicative combinations of these factors. Then, we have:
2^0 * 3^0 = 1
2^1 * 3^0 = 2
2^2 * 3^0 = 4
2^0 * 3^1 = 3
2^1 * 3^1 = 6
2^2 * 3^1 = 12

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

Answer 2

Я не специалист по Python, но для вычисления числа делителей вам нужна простая факторизация числа.

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

Примеры:

12 = 2 ^ 2 * 3 ^ 1 -> Показатели равны 2 и 1, плюс один равен 3 и 2, 3 * 2 = 6 делителей (1,2,3,4,6,12)

30 = 2 ^ 1 * 3 ^ 1 * 5 ^ 1 -> экспоненты 1, 1 и 1, плюс один 2, 2 и 2, 2* 2 * 2 = 8 делителей (1,2,3,5,6,10,15,30)

40 = 2 ^ 3 * 5 ^ 1 -> экспоненты 3 и 1, плюс один4 и 2, 4 * 2 = 8 делителей (1,2,4,5,8,10,20,40)