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

1. 単純な方法: 次の素数を見つけるために、現在の数が素数かどうかを確認しながら数を順番に増やしていく方法です。以下はこの方法の例です。

#include <iostream>
bool isPrime(int number) {
    if (number < 2) {
        return false;
    }
    for (int i = 2; i * i <= number; i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}
int findNextPrime(int currentNumber) {
    int nextNumber = currentNumber + 1;
    while (!isPrime(nextNumber)) {
        nextNumber++;
    }
    return nextNumber;
}
int main() {
    int currentNumber = 10; // 現在の数
    int nextPrime = findNextPrime(currentNumber);
    std::cout << "次の素数: " << nextPrime << std::endl;
    return 0;
}

2. エラトステネスのふるい: エラトステネスのふるいは、与えられた範囲内のすべての素数を見つける効率的な方法です。次のコード例はエラトステネスのふるいを使用して指定された数以下のすべての素数を出力する方法を示しています。

#include <iostream>
#include <vector>
void sieveOfEratosthenes(int n) {
    std::vector<bool> isPrime(n + 1, true);
    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }
    for (int p = 2; p <= n; p++) {
        if (isPrime[p]) {
            std::cout << p << " ";
        }
    }
}
int main() {
    int limit = 100; // 指定された数
    std::cout << limit << "以下の素数: ";
    sieveOfEratosthenes(limit);
    return 0;
}