[C++] 1,000,000番目の素数を求める

素数を見つけろ！

インタプリタ言語よりもコンパイラ言語のほうが速いに決まっているので、どのくらい速いか試してみることにしました。

エラトステネスの篩は2000万くらいの数しか判定できないのと、メモリ使用量がぶっちぎりで多いことから今回は不採用です。

また、ライブラリ関数を使うとこれまたライブラリの最適化の完成度に関わってくるのでこれも今回は不採用です。

要するに同じコードを上手いこと書いてどこまで速くできるかという純粋なパフォーマンス勝負です。

おや、なにやらこのパフォーマンステーブルから不穏な空気を感じ取った方がいらっしゃるようですね？

コンパイラで差はつくか

C++のコンパイラには大御所のgccからVisual Studioで使われるclや、Clangなどいろいろあります。

全部試すのは大変なので今回はgccとclangについて調べました。

gcc

とりあえずぱっとインストールできる安定版を使ってみました。

$ sudo apt install g++
$ g++ -v
gcc version 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04)

今回はgcc version 7.4.0を使用しました

素数リスト

#include <iostream>
#include <time.h>
#include <vector>
using namespace std;
#define N 10000000
vector<int> prime;

bool div(int i)
{
    for (int k = 0; prime[k] * prime[k] <= i; k++)
    {
        if (i % prime[k] == 0)
            return false;
    }
    return true;
}
int main()
{
    prime.push_back(2);
    int i, p;
    double time = clock();

    for (i = 3, p = 1; p < N; i += 2)
    {
        if (div(i))
        {
            prime.push_back(i);
            ++p;
        }
    }
    cout << i - 2 << endl;
    cout << (clock() - time) / CLOCKS_PER_SEC << endl;
}

ソースコードは素数リストのものを使いました。

まずは何も考えずに単純にコンパイルしてみましょう。

$ g++ pn1.cpp
$ ./a.out

その結果がこちら。

これだけでもpypy3を使ったPythonの2.5倍くらい速いのですが実はもっと速くできます。それは、コンパイラの最適化オプションを使うことです。

gccには-O1, -O2, -O3, -Ofastなどのオプションを付けることで最適度を上げてプログラムを高速化することができます。

一番速いのは-Ofastですが、最適化するために少々コンパイルに時間がかかります。まあ、この程度のプログラムなら時間がかかると言っても余計に0.1秒くらいかかるだけなので、完全にオプションは付け得です。

ということで3倍くらい速くなりました。

これなら1000万番目も求められるのでは？と思ったので実行してみることにしました。

すると48.77sで求めることができました。ちなみに答えは179424673でした。

https://primes.utm.edu/curios/page.php/179424673.html

primes.utm.edu

このページによると、どうもこれで合っているみたいです。やったね。

clang++

gccと同様にこちらもインストールします。

以前やねうら王をビルドするときに使ったので元々入っていたのですが…

$ sudo apt install clang++
$ clang++ -v
clang version 6.0.0-1ubuntu2 (tags/RELEASE_600/final)

最適化オプションをつけたものも一度に公開。

まあこのあたりはほとんどgccと差がありませんが、わずかにgccの方が速い様子。

1000万番目を求めたところgccが48.77秒だったのに対してclangは53.40秒かかりました。これはやっぱり有意にgccの方が速い？

ミラーラビン素数判定法

ソースコードはのちのち公開するとして、実際に試してみました。

なんと1000万番目検索の時点でミラーラビンが素数リストよりも速くなりました！！

言語別速度リスト

実行環境は全てAWSなのでマシンスペックに差はありません。

ちなみにセコいのでエラトステネスの篩は使っていません。

C++のぶっちぎりっぷりに震えろ！！！！！

まとめ

ミラーラビンを自力で実装したが、高速に動作できてよかった。

累乗の剰余を求めるところはもっと高速化できるらしいのだがぱっと思いつかなかったのでここまでとする。