ZeroJudge 解題筆記：c033. 00406 - Prime Cuts

作者：王一哲
日期：2026年2月2日


ZeroJudge 題目連結：c033. 00406 - Prime Cuts

解題想法

這個題目的 1 被視為質數。質數表最大值到 1009，因為測資的 n 最大值為 1000，如果只建到 1000，在質數表中用二分搜尋法找 n 可能會出界。

Python 程式碼

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

import sys, bisect

nums = [1]
state = [True]*1010
for i in range(2, 1010):
    if not state[i]: continue
    nums.append(i)
    for j in range(i+i, 1010, i):
        state[j] = False

first = True
for line in sys.stdin:
    n, c = map(int, line.split())
    if not first: print()
    first = False
    idx = bisect.bisect_left(nums, n)
    if nums[idx] == n: k = idx + 1
    else: k = idx
    if (k%2 == 0 and 2*c >= k) or \
       (k%2 == 1 and 2*c + 1 >= k):
        sub = nums[:k]
    elif k%2 == 0: sub = nums[k//2 - c : k//2 + c]
    else: sub = nums[(k+1)//2 - c : k//2 + c]
    print(f"{n:d} {c:d}: ", end="")
    print(*sub)

C++ 程式碼

使用時間約為 2 ms，記憶體約為 268 kB，通過測試。

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

int main() {
    /* 建立 1 ~ 1009 的質數表，本題 1 被當成質數 */
    vector<int> nums = {1};
    vector<bool> state (1010, true);
    for(int i=2; i<1010; i++) {
        if (!state[i]) continue;
        nums.push_back(i);
        for(int j=i+i; j<1010; j+=i) state[j] = false;
    }
    /* 主要的解題過程 */
    bool first = true;
    int n, c;
    while(scanf("%d %d", &n, &c) != EOF) {
        if (!first) puts("");
        first = false;
        printf("%d %d: ", n, c);
        int idx = lower_bound(nums.begin(), nums.end(), n) - nums.begin(), k;
        if (nums[idx] == n) k = idx + 1;  // n 在結尾處
        else k = idx;
        if ((k%2 == 0 && 2*c >= k) || (k%2 == 1 && 2*c + 1 >= k)) {
            for(int i=0; i<k-1; i++) printf("%d ", nums[i]);
            printf("%d\n", nums[k-1]);
        } else if (k%2 == 0) {
            for(int i = k/2 - c; i < k/2 + c - 1; i++) printf("%d ", nums[i]);
            printf("%d\n", nums[k/2 + c -1]);
        } else {
            for(int i = (k+1)/2 - c; i < k/2 + c - 1; i++) printf("%d ", nums[i]);
            printf("%d\n", nums[k/2 + c -1]);
        }
    }
    return 0;
}