算法訓練 Torry的困惑：前 100000 個質數乘積模 50000

算法訓練「Torry的困惑」：求前 n 個質數乘積模 50000 (n ≤ 100000)。本文介紹埃氏篩法預計算質數，利用同餘定理逐步乘積取模，避免大數溢出。

核心數學：同餘定理

(a * b) % m = ((a % m) * (b % m)) % m。
乘積過程中每步取模，中間結果始終 < 50000² = 2.5×10⁹，32 位有符號整數可存（但建議用 64 位防溢出）。

質數篩選：埃氏篩法

第 100000 個質數約為 1299709，篩選上限設 1300000 或 2000000 保險。
篩選得所有質數存入數組 primes[]。

完整代碼（C++）

#include <cstdio>
#include <cstring>
using namespace std;

const int MAXS = 2000000;
const int MOD = 50000;

int main() {
    int n; scanf("%d", &n);
    static bool isPrime[MAXS];
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i < MAXS; ++i)
        if (isPrime[i])
            for (int j = i * i; j < MAXS; j += i)
                isPrime[j] = false;

    long long ans = 1;
    int cnt = 0;
    for (int i = 2; i < MAXS && cnt < n; ++i) {
        if (isPrime[i]) {
            ans = (ans * (i % MOD)) % MOD;
            ++cnt;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

關鍵細節

1. 篩選上限：第 100000 個質數 = 1299709，設 2000000 絕對安全。
2. 64 位中轉：ans * (i % MOD) 最大 < 50000 × 50000 = 2.5×10⁹，32 位有符號上限 2.1×10⁹ 會溢出，必須用 long long。
3. 同餘逐步取模：每乘一個質數即取模，避免大數。
4. 靜態數組：static bool isPrime[MAXS] 放全局/靜態區，避免棧溢出。

Java 版本

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        final int MAXS = 2000000;
        final int MOD = 50000;
        boolean[] isPrime = new boolean[MAXS];
        java.util.Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i < MAXS; ++i)
            if (isPrime[i])
                for (int j = i * i; j < MAXS; j += i)
                    isPrime[j] = false;
        long ans = 1;
        int cnt = 0;
        for (int i = 2; i < MAXS && cnt < n; ++i)
            if (isPrime[i]) {
                ans = (ans * (i % MOD)) % MOD;
                ++cnt;
            }
        System.out.println(ans);
    }
}

總結

本題考察三個基礎知識點：

1. 埃氏篩法 快速生成質數表。
2. 同餘定理 將大數乘積轉化為逐步取模。
3. 數據類型選擇：中間乘積需 64 位防溢出。

代碼極短，關鍵在於正確設置篩選上限並使用 long long 累積答案。此模板適用於所有「前 n 個質數乘積/和 取模」問題。