Project Euler 7

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

Haskellなら、

is_prime n = all (\p -> mod n p /= 0) (takeWhile (\p -> p * p <= n) primes)
primes = 2:(filter is_prime [3,5..])
n = 10001
pair = head (filter (\(k,_) -> k == n) (zip [1..] primes))
main = print (snd pair)

all,takewhile,head,zipを定義したが、うまくいかないところが。

is_prime n = all (\p -> mod n p /= 0) (takeWhile (\p -> p * p <= n) primes)

takeWhileの引数は今のシステムはラムダでなく関数なのでnを渡せない。
今回はprimesに最初から上限をつけて回避した。あるいは別の引数をまとめて構造体にしてポインタで渡すか。できればラムダが使えるようにしたいが策が見つからない。

itertools.h

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

using namespace std;
using namespace itertools;

const int   N = 10001;

vector<int> primes(1, 2);
bool is_prime(int n);

class genPrimes : public cGenerator<int> {
    int k;
    int limit;
    
public:
    genPrimes() : k(0), limit(-1) { }       // 素数の大きさの制限なし
    genPrimes(int l) : k(0), limit(l) { }
    int next() {
        int p;
        // 他でprimesが成長しているかもしれないので
        // 毎回サイズをチェックする
        // マルチスレッドでは使えない
        if(k < (int)primes.size()) {
            p = primes[k];
        }
        else {
            p = head(new filter<int>(
                        is_prime, new count<>(primes[k-1] + 1)));
            primes.push_back(p);
        }
        
        k++;
        if(p <= limit || limit == -1)
            return p;
        else
            throw(1);
    }
    genPrimes *copy() const { return new genPrimes(limit); }
};

bool is_prime(int n) {
    return all([n](int p) { return n % p != 0; },
                            new genPrimes((int)sqrt((double)n)));
}

bool is_reached(tuple<int,int> x) {
    return get<0>(x) == N;
}

int main() {
    auto    t = head(new filter<tuple<int,int>>(is_reached,
                new zip<int,int>(new count<int>(1), new genPrimes())));
    cout << get<1>(t) << endl;
}