Project Euler 3

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

素因数分解をする。
C++ではタプルが使えるのでこれを使う、pairでもいいが。

#include <iostream>
#include <tuple>

using namespace std;

typedef tuple<int,int>  Fact;

int main() {
    Fact    f = Fact(2, 3);
    cout << get<0>(f) << endl;
}

素因数分解を再帰にしたら、かえってややこしくなるだけだった。

#include <iostream>
#include <tuple>

using namespace std;

const long long N = 600851475143;

typedef tuple<long long,int>    Fact;

template<typename T>
class cGenerator {
public:
    virtual ~cGenerator() { }
    virtual T next() = 0;
};

template<typename T>
auto last(T *g) -> decltype(g->next()) {
    auto    v = g->next();
    while(true) {
        try {
            v = g->next();
        }
        catch(int e) {
            delete g;
            return v;
        }
    }
}

class factorize : public cGenerator<Fact> {
    Fact    f;
    factorize   *fs;
    bool    first;
    
public:
    factorize(long long n) {
        first = true;
        
        for(long long p = 2; p * p <= n; p++) {
            int e = 0;
            while(n % p == 0) {
                n /= p;
                e++;
            }
            if(e > 0) {
                f = Fact(p, e);
                fs = new factorize(n);
                return;
            }
        }
        f = Fact(n, 1);
        fs = NULL;
    }
    
    Fact next() {
        try {
            if(first) {
                first = false;
                return f;
            }
            else {
                if(fs == NULL)
                    throw(1);
                return fs->next();
            }
        }
        catch(int e) {
            delete fs;
            throw(1);
        }
    }
};

int main() {
    cout << get<0>(last(new factorize(N))) << endl;
}