HLJ 1171 大素數判定：預篩√N + 試除法

問題描述

多測試用例，每個給一個 n (< 10⁹)，判斷是否為素數。輸出 YES/NO。

算法策略：預篩小質數 + 試除

直接試除到 √n (≤ 31623) 即可，但多測試用例下重複試除慢。優化：
1. 埃氏篩預處理所有 ≤ 50000 的質數（約 5000 個）。
2. 判斷 n 時，只用這些質數試除到 √n。
3. n < 2 直接非素數。

代碼實現

const int MAXP = 50000;
bool isPrime[MAXP+1];
vector primes;

void sieve() {
    fill(isPrime, isPrime+MAXP+1, true);
    isPrime[0]=isPrime[1]=false;
    for (int i=2;i*i<=MAXP;++i)
        if (isPrime[i])
            for (int j=i*i;j<=MAXP;j+=i)
                isPrime[j]=false;
    for (int i=2;i<=MAXP;++i) if (isPrime[i]) primes.push_back(i);
}

bool is_prime(int n) {
    if (n < 2) return false;
    int limit = sqrt(n);
    for (int p : primes) {
        if (p > limit) break;
        if (n % p == 0) return false;
    }
    return true;
}

int main() {
    sieve();
    int n;
    while (scanf("%d", &n) != EOF) {
        puts(is_prime(n) ? "YES" : "NO");
    }
    return 0;
}

複雜度分析

• 預處理：O(MAXP log log MAXP) ≈ 5×10⁴，極快。
• 單次查詢：O(π(√n)) ≈ 3400 次取模，微秒級。

總結

HLJ 1171 是大數素性測試的入門題。對於 n < 10⁹，預篩 √n 內質數再試除是最簡單高效的方法。若 n 更大（如 10¹⁸），需用 Miller-Rabin 等概率算法。