C 语言第22题：输出区间内所有素数

题目

从标准输入读入两个正整数 a 和 b（保证 a ≤ b），输出闭区间 [a, b] 内的所有素数。

输入格式：一行输入两个正整数 a 和 b，以空格分隔。

输出格式：按升序输出区间内的所有素数，每行输出一个，末尾换行。若区间内无素数则不输出。

数据范围与约定：1 ≤ a ≤ b ≤ 10000。

思路与算法

1. 区间遍历与判素模块化
外层循环遍历区间 [a, b] 中的每个整数 x，内层调用素数判定逻辑。将判素逻辑封装为独立函数 is_prime(int n) 使主程序结构清晰。

2. 性能考量
在 b ≤ 10000 规模下，单数试除法耗时极少；若区间扩展到 10⁶ 以上，可换用埃拉托斯特尼筛法（埃氏筛）。

完整程序

#include <stdio.h>

// 单独抽离判素函数：小于 2 不是素数，试除到 √n
static int is_prime(int n)
{
    if (n < 2) {
        return 0;
    }
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

int main(void)
{
    int a, b;
    if (scanf("%d %d", &a, &b) != 2) {
        return 1;
    }

    // 遍历闭区间 [a, b] 逐个筛选素数
    for (int i = a; i <= b; i++) {
        if (is_prime(i)) {
            printf("%d\n", i);
        }
    }
    return 0;
}

运行示例

输入：

10 20

输出：

11
13
17
19

其它写法

下面每种写法都是完整程序，输入输出格式与正文一致，便于对照。

埃氏筛预处理

程序：

#include <stdio.h>
#include <string.h>

int main(void)
{
    int a, b;
    if (scanf("%d %d", &a, &b) != 2) {
        return 1;
    }
    if (b < 2) {
        return 0;
    }
    if (a < 2) {
        a = 2;
    }
    char is_p[1001];
    memset(is_p, 1, sizeof is_p);
    is_p[0] = is_p[1] = 0;
    for (int i = 2; i * i <= b; i++) {
        if (!is_p[i]) {
            continue;
        }
        for (int j = i * i; j <= b; j += i) {
            is_p[j] = 0;
        }
    }
    for (int i = a; i <= b; i++) {
        if (is_p[i]) {
            printf("%d\n", i);
        }
    }
    return 0;
}

输入：

10 20

输出：

11
13
17
19