HDU 1319 Prime Cuts：素數區間輸出格式控制詳解

HDU 1319 考察素數篩選與精確的輸出格式控制。給定 n 和 c，在 1~n 的素數中（注意：1 視為素數），從中間向兩側擴展輸出指定數量的素數。

題目規則

• 統計 1~n 內素數個數 cnt
• 輸出數量 need = (cnt%2==0) ? 2*c : 2*c-1
• 若 need ≥ cnt，全輸出
• 否則從中間向兩側取 need 個：前側 need/2，後側 need - need/2
• 每行輸出結束有空行

關鍵邏輯：確定輸出區間

int cnt = 0;
for (int i = 1; i <= n; i++) if (isPrime[i]) cnt++;

int need = (cnt % 2 == 0) ? 2*c : 2*c - 1;
if (need >= cnt) { output all; continue; }

int skip = (cnt - need) / 2;           // 前側跳過的素數個數
int printed = 0;
for (int i = 1; i <= n; i++) {
    if (!isPrime[i]) continue;
    if (skip > 0) { skip--; continue; }
    if (printed < need) { print i; printed++; }
    else break;
}

完整 AC 代碼

#include 
#include 
using namespace std;

bool isPrime[1001];

void sieve() {
    memset(isPrime, 0, sizeof(isPrime));
    isPrime[1] = true;  // 題目規定 1 是素數
    for (int i = 2; i <= 1000; i++) {
        bool prime = true;
        for (int j = 2; j * j <= i; j++)
            if (i % j == 0) { prime = false; break; }
        isPrime[i] = prime;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    sieve();
    int n, c;
    while (cin >> n >> c) {
        int cnt = 0;
        for (int i = 1; i <= n; i++) if (isPrime[i]) cnt++;

        int need = (cnt % 2 == 0) ? 2*c : 2*c - 1;
        cout << n << " " << c << ":";

        if (need >= cnt) {
            for (int i = 1; i <= n; i++)
                if (isPrime[i]) cout << " " << i;
        } else {
            int skip = (cnt - need) / 2;
            int printed = 0;
            for (int i = 1; i <= n; i++) {
                if (!isPrime[i]) continue;
                if (skip > 0) { skip--; continue; }
                if (printed < need) { cout << " " << i; printed++; }
                else break;
            }
        }
        cout << "\n\n";
    }
    return 0;
}

格式控制要點

測試樣例

Input:
21 2
18 2
0 0

Output:
21 2: 5 7 11 13 17

18 2: 3 5 7 11 13 17

// 21以內素數(含1): 1,2,3,5,7,11,13,17,19 (9個,奇數)
// need=2*2-1=3, skip=(9-3)/2=3, 跳過1,2,3 → 輸出5,7,11

常見錯誤

• 忘記 1 是素數
• need 計算錯誤（奇偶判斷反了）
• 輸出格式多/少空格、少空行
• 未處理 need ≥ cnt 全輸出情況
• 素數篩上界不夠（需 ≥ 1000）

優化建議

• 用埃氏篩預計算 1000 以內素數，O(n log log n) 一次性完成
• 預存素數列表 primes[]，查詢時直接下標訪問
• 邊界情況：c=0（輸出空）、n=1（只有 1）

結語

HDU 1319 算法簡單，難點在繁瑣的格式控制與邊界條件。競賽中此類題建議：先寫出清晰邏輯，再用樣例逐字符核對格式，最後補全邊界測試。養成「輸出格式即代碼一部分」的習慣，能避免大量 PE（Presentation Error）。