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

题目

判断一个数是否为素数

思路

本题判断一个数是否为素数（大于 1 且只能被 1 和自身整除）。

若 n<2 则不是素数。否则用 i 从 2 试到 sqrt(n)（或 i*i<=n），若存在整除则不是；全部试完则是素数。

解题分析

素数判断只需试到 √n：若存在因子 d，则 n/d 也成对出现，较小那个不超过 √n。n<2 直接否，2 单独是素数，偶数大于 2 可直接否再试奇数因子。

完整程序

#include <stdio.h>

int main(void)
{
    int n;
    if (scanf("%d", &n) != 1) {
        return 1;
    }
    if (n < 2) {
        printf("no\n");
        return 0;
    }
    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