题目分析

题目要求

给定一个整数 ( N )，找出 ( 1 ) 到 ( N ) 之间的所有质数，然后根据质数列表的长度（设为 ( L )）和给定的整数 ( C )，按以下规则截取中间的质数：

• 若 ( L ) 为偶数，截取中间的 ( C \times 2 ) 个质数。
• 若 ( L ) 为奇数，截取中间的 ( (C \times 2 - 1) ) 个质数。
• 若截取长度超过实际质数数量，直接输出所有质数。

输入输出格式

• 输入：每行包含两个整数 ( N ) 和 ( C )。
• 输出：按格式输出 ( N )、( C )、截取的质数列表，每行末尾需有一个空行。

代码思路

1. 质数预处理（埃拉托斯特尼筛法）

• 使用筛法预处理 ( 1 ) 到 ( 1100 ) 的质数，存储在数组 PrimeNum 中，其中 PrimeNum[i] 表示第 ( i ) 个质数（下标从 ( 1 ) 开始）。
• Prime 数组标记是否为质数，PrimeNum 数组存储质数列表，同时记录质数总数 num。

2. 确定质数列表长度

• 对于给定的 ( N )，找到最大的下标 pos，使得 PrimeNum[pos] \leq N，即确定 ( 1 ) 到 ( N ) 之间的质数个数为 pos。

3. 计算截取范围

• 情况1：若 ( C \times 2 > pos )（偶数）或 ( C \times 2 - 1 > pos )（奇数），说明截取长度超过实际质数数量，直接输出所有质数。
• 情况2：根据奇偶性计算中间截取的起始和结束下标：
  • 偶数长度（pos 为奇数）：中间有 ( 2k+1 ) 个质数，截取中间的 ( 2C-1 ) 个，起始下标为 ( \frac{pos - (2C-1)}{2} + 1 )，结束下标为 ( \frac{pos - (2C-1)}{2} + (2C-1) )。
  • 奇数长度（pos 为偶数）：中间有 ( 2k ) 个质数，截取中间的 ( 2C ) 个，起始下标为 ( \frac{pos - 2C}{2} + 1 )，结束下标为 ( \frac{pos - 2C}{2} + 2C )。

代码解析

预处理质数

int IsPrime() {
    for (int i = 1; i <= 1100; i++)
        Prime[i] = 1; // 初始化为质数
    Prime[1] = 0; // 1不是质数
    for (int i = 2; i <= 1100; i++) {
        if (Prime[i]) { // 若i是质数，筛去其倍数
            for (int j = i + i; j <= 1100; j += i)
                Prime[j] = 0;
        }
    }
    int num = 0;
    for (int i = 2; i <= 1100; i++) // 收集质数（从2开始）
        if (Prime[i])
            PrimeNum[++num] = i; // PrimeNum[1]存储最小质数2
    return num; // 返回质数总数
}

主函数逻辑

int main() {
    int num = IsPrime(); // 预处理质数
    int N, C, pos;
    while (~scanf("%d%d", &N, &C)) { // 循环读取输入
        pos = 0;
        // 找到最大的pos，使得PrimeNum[pos] <= N
        for (int i = 1; i <= num; i++) {
            if (PrimeNum[i] > N) break;
            pos = i; // 更新pos为最后一个不超过N的质数下标
        }
        printf("%d %d:", N, C);
        if (pos == 0) { // 无质数（N<2）
            printf("\n\n");
            continue;
        }
        int len = pos; // 实际质数个数
        int half;
        if (C * 2 > len && len % 2 == 0) { // 偶数长度且C过大
            half = len / 2;
        } else if (C * 2 - 1 > len) { // 奇数长度且C过大
            half = (len + 1) / 2;
        } else {
            if (len % 2 == 1) { // 奇数长度，截取2C-1个
                half = C * 2 - 1;
            } else { // 偶数长度，截取2C个
                half = C * 2;
            }
        }
        int start, end;
        if (len % 2 == 1) { // 奇数长度，中间有奇数个质数
            start = (len - half) / 2 + 1; // 起始下标（数组从1开始）
            end = start + half - 1;
        } else { // 偶数长度，中间有偶数个质数
            start = (len - half) / 2 + 1;
            end = start + half - 1;
        }
        // 输出结果，确保下标不越界
        start = start < 1 ? 1 : start; // 防止start小于1
        end = end > len ? len : end; // 防止end超过len
        for (int i = start; i <= end; i++)
            printf(" %d", PrimeNum[i]);
        printf("\n\n"); // 每行末尾空行
    }
    return 0;
}

注意事项

1. 质数数组下标：PrimeNum 从下标 ( 1 ) 开始存储质数（如 PrimeNum[1]=2，PrimeNum[2]=3），需注意循环边界。
2. 边界情况：
   • 当 ( N < 2 ) 时，无质数，直接输出空行。
   • 当 ( C ) 过大时，直接输出所有质数，无需截取。
3. 输出格式：每个质数前有一个空格，行末需有一个空行，严格遵循题目示例格式。

该代码通过预处理质数列表，高效处理每个输入案例，确保在 ( N \leq 1000 ) 时快速响应。