炫意html5
最早CSS3和HTML5移动技术网站之一

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

炫意HTML5 » C语言循环结构 -C语言判断素数(质数)

Java基础教程Android基础教程