实验四_循环结构程序设计(4)

第1步，逐一验证除1和它本身之外数能否整除该数。若该数为m，则验证从2开始至m-1为止的所有数能否整除该数。

第2步，得出结论。由第1步可知若其中有一个数能整除该数，则该数不是素数，否则是素数。

将问题的所有可能的情况逐一验证，直到找到解或将全部可能的情况都测试为止的算法，称为穷举法。穷举法是程序设计中常用的算法之一。穷举算法特点是算法简单，但运行时所花费的时间量大。

穷举法在程序设计中，主要采用循环语句和选择语句，循环语句用于控制穷举所有可能的情况，也可以说是对所有可能进行验证的范围，而选择语句判断当前设定的条件是否满足的状态解。

采用穷举法编程实现判断整数m是否是素数。程序设计的循环语句控制验证范围，1到m-1。选择语句的条件就是判断该数能否被1到m-1的数整除，若验证有一个数能整除该数，就立刻中断循环退出验证过程。

由此循环语句退出，一种可能是所有的可能都验证完退出，即从2到m-1的所有数都验证完，没有一个数能整除数m，其结论是数m是素数；另一种可能是其中一个数能整除该数，则循环语句中断退出，其结论是数m不是素数。

#include <stdio.h>

void main( )

{

int m,i;

printf("Please enter a integer\n");

scanf("%d",&m);

for(i=2;i<=m-1;i++)

if(m%i==0) break;

if(i<m) printf("NO\n");

else printf("YES\n");

}

第一次运行程序：

输入测试数据：23

程序运行结果：YES

第二次运行程序：

输入测试数据：145

程序运行结果：NO

小结：

1. 验证m是否是素数的范围：2到m-1或2到m/2或2到m。

2. 在验证过程中，当有一个数能整除数m，则其后的数就不必验证，可由break语句

中断该循环。

3. break 语句只能用在switch语句和循环语句，在循环语句中使用break语句时，通

常和if语句连用，其含义是满足某个条件时，退出循环。

4. 当循环退出时，循环控制变量i的值，决定了数m到底是不是素数。当i<m时，说

明执行循环体时由break语句中断而退出循环，即m能被i整除，m不是素数，反之，当i>=m时，m是素数。