C++ 實現費馬小定理素數測試（概率性）

原理

費馬小定理：若 p 為素數，對任意 1 ≤ a < p，有 a^(p-1) ≡ 1 (mod p)。反之不一定成立（存在偽素數），但可作為概率性測試：隨機選取多個 a 驗證，全通過則極大概率為素數。

代碼

#include <bits/stdc++.h>
using namespace std;
long long mod_pow(long long a, long long e, long long mod) {
    long long res = 1;
    a %= mod;
    while (e) {
        if (e & 1) res = (__int128)res * a % mod; // 防溢出用 __int128
        a = (__int128)a * a % mod;
        e >>= 1;
    }
    return res;
}
bool is_prime(long long n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    // 100 次隨機測試
    for (int i = 0; i < 100; i++) {
        long long a = 2 + rand() % (n - 3);
        if (mod_pow(a, n - 1, n) != 1) return false;
    }
    return true;
}
int main() {
    srand(time(0));
    long long n;
    while (cin >> n) cout << (is_prime(n) ? "yes" : "no") << endl;
    return 0;
}

注意

• 使用 __int128 避免 64 位乘法溢出（GCC/Clang 支持）。
• 測試次數 100 次，錯誤概率 < 2^-100，工程上足夠。
• 確定性測試可用 Miller-Rabin（配合特定基數集）。