C++ 素數判斷入門：試除法優化至 √n 完整實現

題目描述

輸入一個大於 1 的正整數 n，判斷是否為素數。輸出 yes 或 no。

算法原理：試除法

若 n 為合數，必存在因子 d ≤ √n。因此只需檢查 2 ~ √n 是否能整除 n。

優化要點

1. 排除 n = 1（非素數）
2. 2 是唯一偶素數，先判斷 n % 2 == 0
3. 後續只檢查奇數因子 3, 5, 7... ≤ √n
4. 更進階：6k±1 優化、Miller-Rabin (大數)

標準實現

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;

    int limit = static_cast(sqrt(n));
    for (int i = 3; i <= limit; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    cout << (isPrime(n) ? "yes" : "no") << endl;
    return 0;
}

複雜度分析

• 時間：O(√n) —— 10⁹ 以內極快，10¹² 需優化
• 空間：O(1)

進階優化版本

6k ± 1 優化

除 2、3 外，所有素數形如 6k±1。跳過 6 的倍數：

bool isPrimeFast(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;

    for (int i = 5; i * 1LL * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

預計算小素數表 (篩法)

const int MAXP = 1000000;
vector primes;
bitset is_composite;

void sieve() {
    for (int i = 2; i <= MAXP; ++i) {
        if (!is_composite[i]) primes.push_back(i);
        for (int p : primes) {
            if (1LL * i * p > MAXP) break;
            is_composite[i * p] = true;
            if (i % p == 0) break;
        }
    }
}

bool isPrimeSieve(long long n) {
    if (n <= MAXP) return !is_composite[n];
    for (int p : primes) {
        if (1LL * p * p > n) break;
        if (n % p == 0) return false;
    }
    return true;
}

大數素性測試 (n > 10¹²)

採用 Miller-Rabin 概率算法 (確定性版本對 64 位整數僅需測試 12 個基數)：

using u64 = unsigned long long;
using u128 = __uint128_t;

u64 mod_mul(u64 a, u64 b, u64 mod) { return (u128)a * b % mod; }
u64 mod_pow(u64 a, u64 d, u64 mod) {
    u64 r = 1;
    while (d) { if (d & 1) r = mod_mul(r, a, mod); a = mod_mul(a, a, mod); d >>= 1; }
    return r;
}

bool millerRabin(u64 n) {
    if (n < 2) return false;
    for (u64 p : {2,3,5,7,11,13,17,19,23,29,31,37}) {
        if (n % p == 0) return n == p;
    }
    u64 d = n - 1, s = 0;
    while ((d & 1) == 0) { d >>= 1; ++s; }
    for (u64 a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
        if (a % n == 0) continue;
        u64 x = mod_pow(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool composite = true;
        for (u64 r = 1; r < s; ++r) {
            x = mod_mul(x, x, n);
            if (x == n - 1) { composite = false; break; }
        }
        if (composite) return false;
    }
    return true;
}

總結建議

本題為入門級，標準試除法至 √n 完全足夠。掌握遞進優化思路，為後續大數素性測試打基礎。