素数

Haskellの実装の例でよく出てくる素数の計算。こんな感じの。

import System.Environment

primes = sieve [2..]
  where
    sieve (a:as) = a:(sieve [x | x <- as, x `mod` a /= 0])

-- コマンドラインで計算する素数の数を指定。
-- 指定がないときは10個まで計算。
main = do
  a <- getArgs
  let n = if a /= [] then read $ head a else 10
  mapM_ (putStrLn.show) $ take n primes

これをC++で実装するとどれぐらい面倒か比べてみたくなり、試してみた。

#include <iostream>
#include <vector>

#include <boost/lexical_cast.hpp>
#include <boost/lambda/lambda.hpp>

using namespace boost;
using namespace boost::lambda;

class Primes
{
public:
    Primes() : primes_(), current_(1)
    {
    }

    int next()
    {    
        ++current_;
        while(std::find_if(primes_.begin(), primes_.end(), current_ % _1 == 0) != primes_.end())
        {
            ++current_;
        }
        primes_.push_back(current_);
        return current_;
    }

private:
    std::vector<int> primes_;
    int              current_;
};

int main(int argc, char* argv[])
{
    int    n = argc > 1 ? lexical_cast<int>(argv[1]) : 10;
    Primes p;

    for(int i = 0; i < n; ++i)
    {
        std::cout << p.next() << '\n';
    }

    return 0;
}

Mac OS X 10.4.11 / PowerPC G4 1.33GHzで10000番目までの素数を計算させてみたところ。

C++版: 41sec
Haskell版: 73sec

こんなベタな実装でもC++の方が早いことに、ちょっと驚き。