ZeroJudge 解題筆記：a007.判斷質數

作者：王一哲
日期：2026年9月17日


ZeroJudge 題目連結：a007.判斷質數

解題想法

這題要判斷讀取到的整數 $x$ 是否為質數，且 $2 \leq x \leq 2147483647$，最大值為 int 的上限。由於測資為多筆輸入，且最多有 $200000$ 筆，需要想辦法加速才行。這題的提示是建表，出題者的意思是建一個 $46340$ 以內的質數表，因為 $\sqrt{2147483647} \approx 46340$，如果要判斷 $x$ 是否為質數，只要用小於 $\sqrt{x}$ 的質數試除，如果 $x$ 可以被某個質數整除，則 $x$ 不是質數；如果所有小於 $\sqrt{x}$ 的質數都無法整除 $x$，則 $x$ 不是質數。所以解題時先用埃拉托斯特尼篩法建 $46340$ 以內的質數表，再用 while 迴圈讀取 $x$ 直到 EOF 為止，取出質數表中小於 $\sqrt{x}$ 的質數試除即可得到答案。但是這題如果用 Python 解題，即使按這個個邏輯寫程式碼也會超時，需要用比較特別的判斷質數方法才能過關。

C++ 程式碼

解題時間約為 0.6 s，使用記憶體約為 3.8 MB。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    const int maxn = 46340;  // sqrt(2147483647)
    vector<bool> sieve (maxn + 1, true);
    sieve[0] = false;
    sieve[1] = false;
    for(int i = 2; i <= (int)sqrt(maxn); i++) {
        if (sieve[i]) {
            for(int j = i*i; j <= maxn; j += i) {
                sieve[j] = false;
            }
        }
    }
    vector<int> primes;
    for(int i = 0; i <= maxn; i++) {
        if (sieve[i]) {
            primes.push_back(i);
        }
    }
    
    int x;
    while(cin >> x) {
        bool is_prime = true;
        for(int p : primes) {
            if (p*p > x) break;
            if (x % p == 0) {
                is_prime = false;
                break;
            }
        }
        cout << (is_prime ? "質數\n" : "非質數\n");
    }
    return 0;
}

解題時間約為 0.6 s，使用記憶體約為 3.6 MB。

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

int main() {
    const int maxn = 46340;  // sqrt(2147483647)
    vector<bool> sieve (maxn + 1, true);
    sieve[0] = false;
    sieve[1] = false;
    for(int i = 2; i <= (int)sqrt(maxn); i++) {
        if (sieve[i]) {
            for(int j = i*i; j <= maxn; j += i) {
                sieve[j] = false;
            }
        }
    }
    vector<int> primes;
    for(int i = 0; i <= maxn; i++) {
        if (sieve[i]) {
            primes.push_back(i);
        }
    }
    
    int x;
    while(scanf("%d", &x) != EOF) {
        bool is_prime = true;
        for(int p : primes) {
            if (p*p > x) break;
            if (x % p == 0) {
                is_prime = false;
                break;
            }
        }
        if (is_prime) puts("質數");
        else puts("非質數");
    }
    return 0;
}