C 语言第21题：判断一个数是否为素数

题目

从标准输入读入一个整数 n，判断其是否为质数（素数）。质数是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的数。

输入格式：一行输入一个整数 n。

输出格式：若是素数输出 yes，否则输出 no，末尾换行。

数据范围与约定：-10⁹ ≤ n ≤ 10⁹。

思路与算法

1. 特殊与非素数拦截
所有小于等于 1 的整数都不是素数；2 是最小的素数，也是唯一的偶素数。

2. 试除法边界 √n
若整数 n 有因数 d，则必有对应因数 n/d，其中较小者必然满足 d ≤ √n。因此试除只需从 2 检查到 i * i ≤ n，一旦整除即可判定合数提前退出，时间复杂度为 O(√n)。

完整程序

#include <stdio.h>

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

    // 0 和 1 既不是素数也不是合数，负数也不是素数
    if (n < 2) {
        printf("no\n");
        return 0;
    }

    // 核心优化：因子成对出现，较小者必 <= √n
    // 用 i * i <= n 替代 sqrt(n)，避免浮点运算开销
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            printf("no\n");
            return 0;
        }
    }

    printf("yes\n");
    return 0;
}

运行示例

输入：

17

输出：

yes

其它写法

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

只试奇数因子

程序：

#include <stdio.h>

int main(void)
{
    int n;
    if (scanf("%d", &n) != 1) {
        return 1;
    }
    if (n < 2) {
        printf("no\n");
        return 0;
    }
    if (n == 2) {
        printf("yes\n");
        return 0;
    }
    if (n % 2 == 0) {
        printf("no\n");
        return 0;
    }
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            printf("no\n");
            return 0;
        }
    }
    printf("yes\n");
    return 0;
}

输入：

17

输出：

yes