素数判定ロジックについての質問です。

Question

エラトステネスの篩のメリットがわかりません。

素数判定ロジックについての実装をしています。

質問

これら2つを見たときにエラトステネスの篩のメリットがわかりません。

• 整数n分のメモリが必要
• nが大きくなったときに対応できない
• 単一のクエリに関しては明らかに後者の実装の判定のが早そう

以上のようなことを感じました。
複数クエリに対応する場合にメリットがあるという認識でよろしいでしょうか？
ご回答いただけると幸いです。

エラトステネスの篩

// エラトステネスの篩, 素数かどうかの配列を作る
vector<bool> prime_array(100005, true);
    prime_array[0] = false;
    prime_array[1] = false;
    for(int i=2; i*i<=100000; i++) {
        if(!prime_array[i]) continue;
        // 素数のn倍(n>1)に関してはfalseにする
        for(int j=i*2; j<=100000; j+=i) {
            prime_array[j] = false;
        }
    }

こちらが単純な素数判定(O(√n))

bool IsPrime(long long num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く
    double sqrtNum = sqrt(num);
    for (long long i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }
    // 素数である
    return true;
}

Comments

[Zuishin]

むしろ、素数かどうかの判定を一回しかしない状況ってありますか？

[episteme]

> 整数n分のメモリが必要
> nが大きくなったときに対応できない

このふたつ、同じこと言うてます。

# ん－...時間計算量と空間計算量のトレードオフやね。

Answer 1

前者は「N以下の素数表を作る」
後者は「nが素数か判定する」

異なる(そもそもやることが違う)ふたつを比較することに意味があるんですか?

[おあそび] 初回を除きめっちゃ速いやつ

bool IsPrime(int num) {
    // エラトステネスの篩, 素数かどうかの配列を作る
    static std::vector<bool> prime_array(100005, true);
    if ( !prime_array[2] ) {
        prime_array[0] = false;
        prime_array[1] = false;
        for (int i = 2; i * i <= 100000; i++) {
            if (!prime_array[i]) continue;
            // 素数のn倍(n>1)に関してはfalseにする
            for (int j = i * 2; j <= 100000; j += i) {
                prime_array[j] = false;
            }
        }
    }
    return prime_array[num];
}

Answer 2

ある数が素数かどうかを毎回ゼロから判定するのが目的であれば、ご認識の通りで正しいかと思います。