C++で素数を見つける方法

以下に、いくつかの方法とそれぞれの方法のコード例を示します。

方法1: 2から順番に数を試すこの方法では、2から始めて順番に数を試し、割り切れる数がない場合は素数と判定します。

#include <iostream>
bool isPrime(int number) {
    if(number < 2) {
        return false;
    }

    for(int i = 2; i < number; i++) {
        if(number % i == 0) {
            return false;
        }
    }

    return true;
}
int main() {
    int limit = 1000;

    for(int i = 2; i <= limit; i++) {
        if(isPrime(i)) {
            std::cout << i << " ";
        }
    }

    return 0;
}

方法2: 2から√nまでの数を試す素数の性質を利用して、2から√nまでの数で割り切れるかどうかを確認する方法です。√nまでの数で割り切れない場合は素数と判定します。

#include <iostream>
#include <cmath>
bool isPrime(int number) {
    if(number < 2) {
        return false;
    }

    int sqrtN = std::sqrt(number);

    for(int i = 2; i <= sqrtN; i++) {
        if(number % i == 0) {
            return false;
        }
    }

    return true;
}
int main() {
    int limit = 1000;

    for(int i = 2; i <= limit; i++) {
        if(isPrime(i)) {
            std::cout << i << " ";
        }
    }

    return 0;
}

方法3: エラトステネスの篩エラトステネスの篩は、与えられた範囲内の素数を効率的に見つけるアルゴリズムです。以下はその実装例です。

#include <iostream>
#include <vector>
void sieveOfEratosthenes(int limit) {
    std::vector<bool> isPrime(limit + 1, true);

    for(int p = 2; p * p <= limit; p++) {
        if(isPrime[p] == true) {
            for(int i = p * p; i <= limit; i += p) {
                isPrime[i] = false;
            }
        }
    }

    for(int p = 2; p <= limit; p++) {
        if(isPrime[p]) {
            std::cout << p << " ";
        }
    }
}
int main() {
    int limit = 1000;
    sieveOfEratosthenes(limit);

    return 0;
}

これらはC++で素数を見つけるための一般的な方法のいくつかです。選択した方法によってパフォーマンスに違いがありますので、使用する場面や制約に応じて適切な方法を選んでください。また、実装においてエラーチェックや最適化などの改善点も考慮することが重要です。