C++11でint、string間の変換が簡単になった

C++11でint、string間の変換が簡単に出来るようになっていた。
これは楽だ。

#include <iostream>

using namespace std;

int main(int argc, char **argv) {
    
    int n = 123456789;
    string s = to_string(n);
    int m = stoi(s);

    cout << s << endl;    // 123456789
    cout << m << endl;    // 123456789

    return 0;
}

σ関数の計算

σ(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;

}

素数 mod 6

2, 3以外の素数pについて、p mod 6 = ± 1 が成り立つ。

らしい。

証明を考えてみた。
素数pは、以下のいずれかの形式で表すことが出来る。
(a) 6 n
(b) 6 n + 1

(c) 6 n + 2

(d) 6 n + 3

(e) 6 n + 4
(f) 6 n + 5

(a)の場合、pは6で割れるため、pは素数という条件に矛盾。
(c)(e)の場合は2で割れ、(d)の場合は3で割れるため、同様に矛盾。
よって、pは6n + 1、6 n + 5のいずれかの形で表される。

いくつかの素数で試してみる。

5 = 6 * 1 - 1
7 = 6 * 1 + 1
11 = 6 * 2 - 1
13 = 6 * 2 + 1
17 = 6 * 3 - 1
19 = 6 * 3 + 1
23 = 6 * 4 - 1
29 = 6 * 5 - 1
.......

エンジニア日記（2）サードパーティのAPIが変わった

　最近、セキュリティ上の関係で使用しているサードパーティのライブラリを急遽バージョンアップすることになった。バージョンアップするとライブラリが提供するコンテナの型や、APIがごっそり変更になってしまい、それらを使用している箇所をすべて書き換えなければいけなくなった。

話を単純化して例を示すと以下のような感じ。もともと

int main() {

    ThirdPartysContainer<string> container;
    container["hoge"] = "fuga";
    cout << container["hoge"] << endl;
    
    return 0;
}

のようにbraketsで要素にアクセスすることができるThirdPartyContainerという（key, value）型のクラスが提供されていた。
しかしバージョンアップすると、bracketsを使ったアクセスが出来なくなり、代わりにgetter/setterを使わなければいけなくなった。

int main() {

    ThirdPartysContainer<string> container;
    container.set("hoge", "fuga");
    cout << container.get("hoge") << endl;
    
    return 0;
}

で、ThirdPartyContainerクラスを使っている箇所を新しいAPIを使うように書き換えろと。
ThirdPartyContainerクラスはいろいろな箇所で使われていて、書き換えるソースは膨大な量になった。さらに、書き換えたソースは動作検証しないといけない。

こんなことにならないようにするためには、サードパーティのクラスを隠蔽して、個々の機能からは見えないようにしておくべきだった。アダプターパターンを使って、将来変更される可能性があるサードパーティのクラスをラッピングしておくべきだったのだ。

template <typename T>
class ThirdPartysContainerWrapper {
    
    ThirdPartysContainer<T> contaier;
    
public:
    
    T getData(const string key) {
        return contaier[key];
    }

    void setData(const string key, const T val) {
        contaier[key] = val;
    }

};

みたいなクラスを作っておいて、個別のクラスからは、

int main() {
    
    ThirdPartysContainerWrapper<string> container;
    container.setData("hoge", "fuga");
    cout << container.getData("hoge") << endl;
    
    return 0;
}

のような使い方をするようにしておけば、改修箇所はラッパークラスだけでよかったのになと。