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

题目

输出区间内所有素数

思路

循环 x 从 L 到 R，调用判素函数或内联试除；注意 L,R 顺序与边界包含。

解题分析

区间内每个数单独试除，在 b-a 不大、上限约 1000 时完全够用。若区间很宽或起点很小，可先用埃氏筛筛到 b，再输出筛表中的位置。

完整程序

#include <stdio.h>

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;
    }
    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