4.6.4  质数

4.6.4 质数

【例4-28】输入一个正整数N，判断是否为质数。

按“三步法”原则分析如下。

做什么

用户需要输入N，所以程序要有输入功能，可以采用一个文本框作为输入。

怎么做

分析：根据质数的定义，除了1和它本身外，不能被任何数整除的数是质数。判断一个数N是否质数的方法是，用N分别去除2～N-1之间的数，如果没有一个数能够被N整除，则N为质数。如果发现存在一个数能够被N整除，则得出N不是质数，这时退出循环，停止判断。

上述方法进行除法运算的次数较多，采用下面的数学方法可以极大减少除法次数：

用N分别去除2～N的平方根之间的整数，如果没有一个数能够被N整除，则N为质数。如果发现存在一个数能够被N整除，则得出N不是质数，这时退出循环，停止判断。

步骤描述如下。

1）获取用户输入数据N。

2）如果N为1，则输出N不是质数，程序结束。

3）初始化控制变量i为2。

4）判断i，如果i小于或等于N的平方根，则继续向下执行，否则执行第8）步。

5）用N除以i，如果余数为0，则退出循环，执行第8）步；否则继续向下执行。

6）i值增1。

7）返回第4）步。

8）判断i值，如果i大于N的平方根，则输出N是质数，程序结束；否则输出N不是质数，程序结束。

实现

●用For语句实现：

●用Do…Loop语句前测型当型结构实现：

●用Do…Loop语句前测型直到型结构实现：

●用Do…Loop语句后测型当型结构实现：

●用Do…Loop语句后测型直到型结构实现：

●用While语句实现：