您当前的位置:首页 > 计算机 > 编程开发 > C语言

C语言判断素数(质数)

时间:10-08来源:作者:点击数:

这是一个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

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门