C++における素数の検出方法

1. ナイーブな方法: 素数を検出する一番単純な方法は、該当の数値を2からその数値自身の平方根までの範囲で割り算し、割り切れるかどうかを確認することです。もし割り切れる数が存在しなければ、その数値は素数です。

以下に、ナイーブな方法を用いた素数検出のコード例を示します:

#include <iostream>
#include <cmath>
bool isPrime(int number) {
    if (number <= 1) {
        return false;
    }
    for (int i = 2; i <= sqrt(number); i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}
int main() {
    int n = 1000;
    std::cout << "Prime numbers up to " << n << " are:" << std::endl;
    for (int i = 2; i <= n; i++) {
        if (isPrime(i)) {
            std::cout << i << " ";
        }
    }
    return 0;
}

2. エラトステネスの篩: エラトステネスの篩（Sieve of Eratosthenes）は、素数を効率的に見つけるためのアルゴリズムです。このアルゴリズムでは、2から始まる数列を順に調べ、素数である場合にはその倍数をすべて除外します。この処理を繰り返すことで、最終的に素数のみが残ります。

以下に、エラトステネスの篩を用いた素数検出のコード例を示します:

#include <iostream>
#include <vector>
void sieveOfEratosthenes(int n) {
    std::vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    std::cout << "Prime numbers up to " << n << " are:" << std::endl;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            std::cout << i << " ";
        }
    }
}
int main() {
    int n = 1000;
    sieveOfEratosthenes(n);
    return 0;
}

これらの方法を使えば、C++で素数を見つけることができます。ナイーブな方法は比較的簡単ですが、大きな数に対しては効率が悪い場合があります。一方、エラトステネスの篩は効率的に素数を見つけることができますが、メモリ使用量が増える可能性があるため、大きな範囲の素数を見つける場合には注意が必要です。

このブログ投稿は、C++における素数の検出方法とそのコード例について詳しく解説しています。