σ関数の計算

σ(n) = sum_{d | n} {d} と定義する。

例えば、σ(28) = 1 + 2 + 4 + 7 + 14+ 28 = 56.
となる。ちなみに、σ(28) - 28 = 28なので、28は完全数。

n = (p1 ^ k1) * (p2 ^ k2) * .... * (pn ^ kn)
のようにnが素因数分解されていれば、σ(n)は以下のように計算出来る。

σ(n) = (1 + p1 + p1^2 + ... + p1^k1) * (1 + p2 + p2^2 + ... + p2^k2) ....
        = (p1^(k1 + 1) - 1) / (p1 - 1)  * (p2^(k2+1) - 1) / (p2 - 1) * ....

上式を使ってσ関数を計算するプログラムをC++で書いてみた。

#include <iostream>
#include <cassert>

using namespace std;

long long sigma(long long x) {

    long long ret = 1;
    
    for (long long i = 2; i * i <= x; i++) {
        if (x % i)
            continue;
        long long p = i;
        while (x % i == 0) {
            p *= i;
            x /= i;
        }
        ret *= (p - 1) / (i - 1);
    }

    if (x > 1)
        ret *= (x * x - 1) / (x - 1);

    return ret;

}

// for debug use only
long long slowerSigma(long long x) {
    long long ret = 0;

    for (long long i = 1; i * i <= x; i++) {
        if (x % i)
            continue;

        ret += i;
        if (i * i != x)
            ret += x / i;
    }

    return ret;
}

int main(int argc, char **argv) {

    // test
    for (int i = 1; i < 1000000; i++) {
        assert(sigma(i) == slowerSigma(i));
    }

    for (;;) {
        long long x;
        cin >> x;
        if (x == -1)
            break;
        cout << sigma(x) << endl;
    }

    return 0;
}

(2014/8/28 追記)等比数列の和のところは下のように書いた方がシンプル。

long long sigma(long long x) {

    long long ret = 1;
    
    for (long long i = 2; i * i <= x; i++) {
        long long p = 1;
        while (x % i == 0) {
            p = p * i + 1;
            x /= i;
        }
        ret *= p;
    }

    if (x > 1)
        ret *= x + 1;

    return ret;

}