HDU 2007 熱身賽：How many prime numbers——質數判定

題目描述

多組測試，每組給 N 個整數（≥2，≤ 2³¹-1），統計質數個數。

判定算法：試除法優化

• 只需試除到 √n
• 2 特判，之後只試奇數
• 更優：預篩小質數表，但單次 √n 試除對 32 位整數已足夠快（√2e9 ≈ 44721）

C++ 實現

#include <cstdio>
#include <cmath>
bool isPrime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    int limit = (int)sqrt(n);
    for (int i = 3; i <= limit; i += 2)
        if (n % i == 0) return false;
    return true;
}
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        int cnt = 0;
        for (int i = 0, x; i < n; ++i) {
            scanf("%d", &x);
            if (isPrime(x)) ++cnt;
        }
        printf("%d\n", cnt);
    }
    return 0;
}

複雜度

• 單數判定：O(√n) ≈ 2.2e4 步
• 總時間：極快通過