// エラトステネスのふるいをC++で実装してみたかった

学校で素数を書き出す課題が出たので実装してみました。

2020/12/18 追記：これは試し割り法です。エラトステネスのふるいの実装例はコメント欄へお願いします。

コード

# include <bits/stdc++.h>
# define rep(i,n) for(auto i=0;i<n;++i)
typedef  unsigned long long ull;

using namespace std;

// 2以上の整数値を引数に取り，素数のvector<ull>を返す
vector<ull> eratosthenes_sieve(ull max_num) {
    vector<ull> int_list;
    vector<ull> searched_list;
    vector<ull> prime_list;
    int_list.reserve(max_num-1);

    rep(i, (int)max_num-1) {
        int_list.push_back(i+2);
    }

    while(int_list[0]*int_list[0] < max_num) {
        ull prime = int_list[0];
        searched_list.push_back(prime);
        auto removeit = remove_if(int_list.begin(), int_list.end(), [&](ull value) {
            return value % prime == 0;
        } );
        int_list.erase(removeit, int_list.end());
    }
    merge(int_list.begin(), int_list.end(), searched_list.begin(), searched_list.end(), back_inserter(prime_list));
    return prime_list;
}

signed main(void) {
    auto prime_list = eratosthenes_sieve(10000000);
    for(const auto& i: prime_list) {
        printf("%llu", i);
        if(i != *(prime_list.end()-1)) printf(", ");
    }
    printf("\n");
    return 0;
}

新しい知見

• vectorの初期化はvector.reserve()でvectorの範囲を指定してからpush_back()すると高速
• remove_if()を使うと条件に一致したvector要素を高速に削除できる
• merge()で2つのvectorを1つのvectorにできる
• vectorの要素がが整数型のとき，*(vector.end()-1)で最終要素が取得できる

よく理解ができなかった部分

• remove_if()が実際にどのような処理をしているのかが理解できなかった

改善していきたい点

• 現状ではシングルスレッド処理なので，並列処理に対応し高速化を図りたい(Arch Linux, Core i5 10210u, N=10^7で13秒程度)

参考文献

vectorの初期化 | Qiita
最速の素数列挙プログラム C# | Qiita
C++日本語リファレンス | cpprefjp
【C++】簡単なvectorテクニック | msty開発メモ