C++で素数判定を高速に実装する方法：O(√n)の基本からエラトステネスの篩まで解説

#include <iostream>

/**
 @brief 素数判定を行う関数 (O(√n))
 @param n 判定対象の整数
 @return 素数であればtrue、そうでなければfalse
 */
bool is_prime(long long n) {
    // 1以下は素数ではない
    if (n <= 1) return false;
    // 2と3は素数
    if (n <= 3) return true;
    // 2または3で割り切れる偶数・倍数は素数ではない
    if (n % 2 == 0 || n % 3 == 0) return false;

    // √nまでループを回す
    // i * i <= n とすることで sqrt() 関数の呼び出しを避ける
    for (long long i = 5; i * i <= n; i += 6) {
        // 6k ± 1 の形以外の数値は既にチェック済みの2や3の倍数
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }

    return true;
}

int main() {
    long long numbers[] = {2, 17, 27, 1000000007, 1000000009};

    for (long long n : numbers) {
        if (is_prime(n)) {
            std::cout << n << " is a prime number." << std::endl;
        } else {
            std::cout << n << " is not a prime number." << std::endl;
        }
    }

    return 0;
}

#include <iostream>
#include <vector>

/**
 @brief エラトステネスの篩を用いてN以下の素数を列挙する
 @param n 最大値
 @return 素数判定結果の配列 (is_prime[i] が true ならば i は素数)
 */
std::vector<bool> sieve_of_eratosthenes(int n) {
    std::vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false; // 0と1は素数ではない

    for (int p = 2; p * p <= n; p++) {
        // pが素数の場合、その倍数をすべて偽にする
        if (is_prime[p]) {
            for (int i = p * p; i <= n; i += p)
                is_prime[i] = false;
        }
    }
    return is_prime;
}

int main() {
    int limit = 50;
    std::vector<bool> primes = sieve_of_eratosthenes(limit);

    std::cout << "Primes up to " << limit << ":" << std::endl;
    for (int i = 2; i <= limit; i++) {
        if (primes[i]) {
            std::cout << i << " ";
        }
    }
    std::cout << std::endl;

    return 0;
}

#include <iostream>
#include <vector>

typedef __int128_t int128;

// 冪剰余計算 (base^exp % mod)
long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (long long)((int128)res * base % mod);
        base = (long long)((int128)base * base % mod);
        exp /= 2;
    }
    return res;
}

/**
 @brief ミラー・ラビン素数判定法
 @param n 判定対象
 @return 素数であればtrue
 */
bool is_prime_miller_rabin(long long n) {
    if (n <= 1) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;

    long long d = n - 1;
    int s = 0;
    while (d % 2 == 0) {
        d /= 2;
        s++;
    }

    // 64ビット整数の範囲で決定論的に判定するために必要な底
    std::vector<long long> bases = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

    for (long long a : bases) {
        if (n <= a) break;
        long long x = power(a, d, n);
        if (x == 1 || x == n - 1) continue;
        
        bool composite = true;
        for (int r = 1; r < s; r++) {
            x = (long long)((int128)x * x % n);
            if (x == n - 1) {
                composite = false;
                break;
            }
        }
        if (composite) return false;
    }
    return true;
}

int main() {
    long long large_prime = 9223372036854775783LL; // 巨大な素数
    if (is_prime_miller_rabin(large_prime)) {
        std::cout << large_prime << " is a prime number." << std::endl;
    } else {
        std::cout << large_prime << " is not a prime number." << std::endl;
    }
    return 0;
}

#include <iostream>

// コンパイル時に評価可能な素数判定関数
constexpr bool is_prime_constexpr(long long n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (long long i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

int main() {
    // コンパイル時定数として結果を保持
    constexpr bool result = is_prime_constexpr(1000000007);
    
    if constexpr (result) {
        std::cout << "1000000007 is prime (checked at compile time)." << std::endl;
    }

    return 0;
}