Найти сумму факторов

Question

Почему этот код возвращает сумму множителей числа?

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

public int sumOfDivisors(int n)
{
    int prod=1;
    for(int k=2;k*k<=n;k++){
        int p=1;
        while(n%k==0){
            p=p*k+1;
            n/=k;
        }
        prod*=p;
    }
    if(n>1)
        prod*=1+n;
    return prod;
}

Теперь, я пробовал это много раз, и я вижу, что это работает. Вопрос в том, почему?

Скажи, что ты фактор 100: 1,2,4,5,10,20,25,50,100. Сумма составляет 217. Основная факторизация 2*2*5*5. Эта функция дает вам [5*(5+1)+1]*[2*(2+1)+1] = [25+5+1]*[4+2+1] = 217

Факторинг 8: 1,2,4,8. Сумма 15. Основная факторизация 2*2*2. Эта функция дает вам [2*(2*(2+1)+1)+1]=15

Алгоритм сводится к (используя Fi для обозначения i-го индекса коэффициента F или F sub i):

return product(sum(Fi^k, k from 0 to Ni), i from 1 to m)

, где m - количество уникальных простых факторов, Ni - количество раз, когда каждый уникальный фактор встречается в простой факторизации.

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

Answer 1

Давайте рассмотрим самый простой случай: когда n - это степень простого числа.

Факторами k^m являются 1, k, k ^ 2, k ^ 3 ... k ^ m-1.

Теперь давайте посмотрим на внутренний цикл алгоритма:

После первой итерации имеем k + 1.

После второй итерации имеем k(k+1) + 1 или k^2 + k + 1

После третьей итерации имеем k^3 + k^2 + k + 1

И так далее ...

---

Вот как это работает для чисел, являющихся степенями одного простого числа. Я мог бы сесть и обобщить это на все числа, но вы могли бы сначала попробовать сами.

РЕДАКТИРОВАТЬ: Теперь, когда это принятый ответ, я подробнее расскажу, как работает алгоритм на числах с двумя различными основными факторами. Тогда будет просто обобщить это на числа с произвольным количеством различных простых факторов.

Коэффициенты x^i.y^j: x^0.y^0, x^0.y^1 ... x^0.y^j, x^1.y^0 ...

Внутренние циклы для каждого отдельного простого множителя генерируют x^i + x^i-1 + ... + x^0 (и аналогично для y). Тогда мы просто умножаем их вместе и получаем сумму множителей.

Answer 2

Алгоритм, по сути, рассматривает множество всех упорядоченных подмножеств простых множителей n, что аналогично множеству множителей n.