Project Euler 3（2）

http://projecteuler.net/index.php?section=problems&id=3

例えば次のようなコードを考える。

#include <iostream>
#include "itertools.h"

using namespace std;
using namespace itertools;

class cCeil {
    int n;
    
public:
    cCeil(int n) : n(n) { }
    int operator()(int m) const {
        return head(filter([n] (int k) { return k >= n; }, count<>(m, m)));
    }
};

int main() {
    cout << cCeil(5)(3) << endl;    // 6のはず
}

これは、n以上で最も小さいmの倍数を返すクラスである。filterの引数にラムダを使っていてnを取り込もうとしているが、エラーになる。
{}内に変数があればよいので次のようにすれば通る。

    int operator()(int m) const {
        int n = this->n;
        return head(filter([n] (int k) { return k >= n; }, count<>(m, m)));
    }

しかし、これよりも手軽なのは、

        return head(filter([&] (int k) { return k >= n; }, count<>(m, m)));

これで、メンバ変数を全て参照で取り込めているらしい。
mapなどラムダ（関数オブジェクト）を引数に取るところで関数を使いたいときは、そのまま関数が使えるようにしてもよかったが、func_objというヘルパ関数を作って関数を関数オブジェクトに変換するようにした。

itertools.h

#include <iostream>
#include "itertools.h"

using namespace std;
using namespace itertools;

typedef tuple<int,int>  Fact;

template<typename T>
class factorize {
    count<> g;
    T       n;
    
public:
    factorize(T n, int start = 2) : n(n), g(count<>(start)) { }
#if 1
    tuple<int,int> next() {
        try {
            int p = head(filter([&] (int p) { return n % p == 0; },
                    takewhile([&] (int p) { return p * p <= n; }, g)));
            int e = 0;
            while(n % p == 0) {
                e++;
                n /= p;
            }
            return Fact(p, e);
        }
        catch(...) {
            int p = n;
            n = 1;
            return Fact(p, 1);
        }
    }
    bool exists_next() {
        return n != 1;
    }
#else
    tuple<int,int> next() {
        if(n == 1)
            throw(1);
        try {
            int p = head(filter([&] (int p) { return n % p == 0; },
                    takewhile([&] (int p) { return p * p <= n; }, g)));
            int e = 0;
            while(n % p == 0) {
                e++;
                n /= p;
            }
            return Fact(p, e);
        }
        catch(int e) {
            int p = n;
            n = 1;
            return Fact(p, 1);
        }
    }
#endif
};

int main() {
    cout << last(map(fst<int,int>,
                        factorize<long long>(600851475143))) << endl;
}