首页 > C语言教程 > C语言循环结构

C语言判断素数（质数）

上一节
这是一个C语言 while 循环的示例：判断一个整数 n（n>1）是否为素数（也成质数）。

问题分析

输入：一个整数n（n>1）。

输出：Yes or No。

如果一个整数 n（n>1）不能被 1 或 n 以外的正整数整除，那么 n 就是素数。因此，只要把 2 至 n-1 之间的每一个数字，分别作为除数，与 n 做除法，只要出现一次整除，就说明 n 不是素数；而一直没有出现整除现象，则说明 n 是素数。

一个整数的因子都是成对出现的，如果 x 能被 n 整除，n 是 x 的因子，x/n 同样是 x 的因子，成对的两个因子中（除了 1 和本身），都不会超过 n/2。因此，上面判断是否为素数时，用作除数的 2 至 n-1 之间的数字个数可以减半，用 2 至 n/2 之间的数字作为除数即可。

再进一步，可以把作为除数的数字范围缩小到 2～sqrt(n)（根号 n）。

另外 2 是最小的素数，直接输出“Yes”即可。大于 2 的整数才用上面的方法进行判断处理。

整除判断部分可以用 do-while 循环语句或者 while 循环语句实现，流程图如图 1 所示。

用 do-while 语句和 while 语句实现整除循环判断的流程图
图 1：用 do-while 语句和 while 语句实现整除循环判断的流程图

算法描述和实现

1) 使用 do_while 语句

do-while 语句的N-S图描述

代码清单 1：使用 do-while 语句判断一个整数 n（n>1）是否为素数 
#include <stdio.h>
#include <stdlib.h>
int main( )
{
    int n,i;
    printf("输入一个大于1的整数：\n");
    scanf("%d",&n);
    if(n == 2) 
        printf("Yes\n");                     //处理 2 的判断
    else                                     //处理 n>2 的判断
    {
        i = 1;
        do
            i++;
        while(n % i != 0 && i <= sqrt(n));   //循环条件
        if(n % i == 0) 
            printf("No\n");                  //出现整除，非素数
        else 
            printf("Yes\n");                 //否则，是素数
    }
    system("pause");
    return 0;
}
do-while 语句在判断之前就执行 i++ 一次，所以 i 的初始值为 1。
运行结果为：

输入一个大于1的整数：
97
Yes

2) 使用 while 语句


while 语句的N-S图描述

代码清单 2：使用 while 语句判断一个整数 n（n>1）是否为素数 
#include <stdio.h>
#include <stdlib.h>
int main( )
{
    int n,i;
    printf("输入一个大于1的整数：\n");
    scanf("%d",&n);
    if(n == 2) 
        printf("Yes\n");                     //处理2的判断
    else                                     //处理n>2的判断
    {
        i = 2;
        while(n % i != 0 && i <= sqrt(n))    //循环条件
            i++;
        if(n % i == 0) 
            printf("No\n");                  //出现整除，非素数
        else 
            printf("Yes\n");                 //否则，是素数
    }
    system("pause");
    return 0;
}

运行结果为：

输入一个大于1的整数：
177
No

上一节