您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> 關於C語言

HDU 1319 Prime Cuts：素數篩選與中心區間輸出的邊界控制技巧

編輯：關於C語言

題目大意

給定 N (≤1000) 和 C。列出 1 到 N 間所有素數 (題目規定 1 也是素數)。設素數總數為 count。需輸出：

若 count 為偶數：輸出中間 2×C 個素數
若 count 為奇數：輸出中間 2×C - 1 個素數
「中間」定義：從素數列表中心向兩側擴展，兩側數量盡量相等；無法均分時前側少 1 個。
若需輸出數量 ≥ count，則全輸出。

格式：N C: p1 p2 ...，每行結束有空行。

核心邏輯：中心區間索引計算

設素數存入數組 primes[0..count-1] (已排序)。

目標輸出數量 target = (count%2==0) ? 2*C : 2*C-1
若 target >= count：全輸出 [0, count-1]
否則：

中心點索引 mid = (count - 1) / 2 (整數除法，向下取整)。
例如 count=5 (索引 0,1,2,3,4) → mid=2 (第 3 個)。
count=6 (0..5) → mid=2 (偏左中心)。

需向左取 L 個，向右取 R 個，滿足 L + R + 1 = target (含中心點)。
題目要求「前側少 1」→ L = (target - 1) / 2, R = target - 1 - L。
驗證：target=5 → L=2, R=2；target=4 → L=1, R=2 (前側少 1)。

輸出區間：[mid - L, mid + R] (閉區間)。

完整 AC 代碼 (C++ 風格，清晰版)


#include 
using namespace std;

const int MAX_N = 1000;
vector primes;
bool is_composite[MAX_N + 1];

void sieve()
{
    fill(begin(is_composite), end(is_composite), false);
    is_composite[0] = is_composite[1] = true; // 0,1 非素數，但題目說 1 是素數！特殊處理
    for (int i = 2; i * i <= MAX_N; i++)
        if (!is_composite[i])
            for (int j = i * i; j <= MAX_N; j += i)
                is_composite[j] = true;

    primes.clear();
    primes.push_back(1); // 題目規定 1 是素數，手動加入
    for (int i = 2; i <= MAX_N; i++)
        if (!is_composite[i]) primes.push_back(i);
}

int main()
{
    sieve();
    int N, C;
    while (cin >> N >> C) {
        // 截取 1..N 內的素數
        vector sub;
        for (int p : primes)
            if (p <= N) sub.push_back(p);
            else break;

        int cnt = sub.size();
        int target = (cnt % 2 == 0) ? 2 * C : 2 * C - 1;

        cout << N << " " << C << ":";

        if (target >= cnt) {
            for (int p : sub) cout << " " << p;
        } else {
            int mid = (cnt - 1) / 2;
            int L = (target - 1) / 2;
            int R = target - 1 - L;
            int start = mid - L;
            int end = mid + R;
            for (int i = start; i <= end; i++)
                cout << " " << sub[i];
        }
        cout << "\n\n"; // 每行後空行
    }
    return 0;
}

關鍵細節與避坑

1 是素數：標準篩法不含 1，必須手動 push_back(1)。這是本題最大陷阱。
預計算篩法：多測試用例，MAX_N=1000 只需篩一次，O(1) 回答查詢。
中心索引計算：mid = (cnt-1)/2 對奇偶 cnt 均正確指向「偏左中心」。
左右分配公式：L = (target-1)/2, R = target-1-L 完美實現「前側少 1」。
邊界檢查：target >= cnt 直接全輸出，避免區間越界。
格式控制：N C: 後每個素數前一空格，行末換行再加一空行 (\n\n)。

手動推演驗證

Case: N=21, C=2
1..21 素數 (含1)：[1,2,3,5,7,11,13,17,19] (cnt=9, 奇數)
target = 2*2-1 = 3
mid = (9-1)/2 = 4 (值 7)
L = (3-1)/2 = 1, R = 3-1-1 = 1
區間 [4-1, 4+1] = [3,5] → 值 3, 5, 7? 等等，sub[3]=5, sub[4]=7, sub[5]=11 → 輸出 5 7 11?
但題目要求「從中心向兩側擴展」。中心是第 5 個素數 (索引4, 值7)。向左1個(5)，向右1個(11)。輸出 5 7 11。
檢查 UVA 1319 / HDU 1319 標準輸出：21 2: 5 7 11 ✅

Case: N=18, C=2
素數：[1,2,3,5,7,11,13,17] (cnt=8, 偶數)
target = 4
mid = (8-1)/2 = 3 (值 5)
L = (4-1)/2 = 1, R = 4-1-1 = 2
區間 [3-1, 3+2] = [2,5] → 值 2,3,5,7,11? 共 5 個？target=4。
錯誤！mid=3 是索引 3 (值 5)。L=1 → 索引 2 (值 3)。R=2 → 索引 4,5 (值 7,11)。共 1+1+2=4 個：3, 5, 7, 11。
但「前側少 1」應為左1右2。輸出 3 5 7 11。標準答案驗證通過。