ZeroJudge 解題筆記：f803. 質數篩法練習

作者：王一哲
日期：2025年10月24日


ZeroJudge 題目連結：f803. 質數篩法練習

解題想法

這題可以用埃拉托斯特尼篩法建質數表，再用二分搜尋找指定的質數在表中的索引值。

Python 程式碼

原來測試時，使用時間約為 2.5 s，記憶體約為 323.6 MB，通過測試。但是在2025年10月23日測試時，最後一筆測資超時，好像沒有為 Python 使用者放寬時間限制，仍然為 1 s。

from bisect import bisect_left

n, m = map(int, input().split())
states = [True]*n
states[0] = states[1] = False
for i in range(2, int(n**0.5) + 1):
    if states[i]:
        states[i+i::i] = [False]*len(states[i+i::i])
primes = [i for i, is_prime in enumerate(states) if is_prime]
for _ in range(m):
    print(bisect_left(primes, int(input())) + 1)

改用 sys 加速並修改內層 for 迴圈的寫法仍然超時。

import sys
from bisect import bisect_left

result = []
lines = sys.stdin.readlines()
n, m = map(int, lines[0].split())
sieve = [True]*n
sieve[0] = sieve[1] = False
for i in range(2, int(n**0.5) + 1):
    if sieve[i]:
        for j in range(i*i, n, i):
            sieve[j] = False
primes = [int(i) for i in range(n) if sieve[i]]
idx = 1
while idx < len(lines):
    x = int(lines[idx])
    idx += 1
    pos = bisect_left(primes, x) + 1
    result.append(f"{pos:d}\n")
sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 53 ms，記憶體約為 8 MB，通過測試。

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

int main() {
    int n, m; scanf("%d %d", &n, &m);
    vector<bool> sieve (n, true);
    sieve[0] = false; sieve[1] = false;
    for(int i=2; i<=int(sqrt(n)); i++) {
        if (sieve[i]) {
            for(int j=i+i; j<n; j+=i) {
                sieve[j] = false;
            }
        }
    }
    vector<int> primes;
    for(int i=2; i<n; i++) {
        if (sieve[i]) primes.push_back(i);
    }
    for(int i=0; i<m; i++) {
        int a; scanf("%d", &a);
        printf("%ld\n", lower_bound(primes.begin(), primes.end(), a) - primes.begin() + 1);
    }
    return 0;
}

使用時間約為 42 ms，記憶體約為 8 MB，通過測試。

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

int main() {
    int n, m; scanf("%d %d", &n, &m);
    vector<bool> sieve (n, true);
    sieve[0] = false; sieve[1] = false;
    for(int i=2; i<=int(sqrt(n)); i++) {
        if (sieve[i]) {
            for(int j=i*i; j<n; j+=i) {
                sieve[j] = false;
            }
        }
    }
    vector<int> primes;
    for(int i=2; i<n; i++) {
        if (sieve[i]) primes.push_back(i);
    }
    for(int i=0; i<m; i++) {
        int a; scanf("%d", &a);
        printf("%ld\n", lower_bound(primes.begin(), primes.end(), a) - primes.begin() + 1);
    }
    return 0;
}