《C编程技巧：117个问题解决方案示例 》 —2.4　确定给定数字是否为质数

2.4　确定给定数字是否为质数

问题

你希望开发一个程序来确定给定的数字是否为质数。

解决方案

质数是一个正整数，只能被1和它本身整除。前几个质数如下：2, 3, 5, 7, 11, 13, 17, 19。除了2之外，所有质数都是奇数。你将开发一个程序来确定给定的数字是否为质数。

程序执行开始时，系统会要求你输入2～2 000 000 000范围内的数字。键入此范围内的任何整数，程序将告诉你此数字是否为质数。另外，输入0以终止程序。显然，要确定数字N是否为质数，必须将它除以2～（N-1）之间的所有数字并检查余数。如果每个除法的余数都不为零，则数N是质数，否则，它不是质数。但是，实际上可以将N的数字除以2～√N（N的平方根）之间的所有数字并检查余数。如果N不能被2～√N之间的任何数字完全整除，那么它肯定不能被2～（N-1）之间的任何数字整除。

此处给出了一个例程，用于确定给定数字lngN是否为质数。这里，isPrime是一个int变量，lngN、lngM和i是long int变量，lngN的值为3或更大，并且isPrime设置为1（被解释为真）。

在此例程的LOC 2中，通过隐式类型转换将lngN的值转换为double类型，然后将其传入sqrt()以计算其平方根。sqrt()返回的结果被传到ceil()以将其转换为较大的最接近的整数。在隐式类型转换后，ceil()返回的结果将赋值给lngM。

接下来，lngN将除以2到lngM之间的所有数字。如果在所有这些除法中余数都为非零，那么lngN是质数，否则不是。这是在LOC 3～8的for循环中完成的。实际除法在LOC 4中执行，并检查余数的值（是否为零）。如果余数为零，则执行LOC 5和6。在LOC 5中，int变量isPrime的值设置为零。在LOC 6中，执行break语句以终止for循环。注意isPrime的值，结果显示在屏幕上。如果isPrime为1（真），则lngN为质数；如果isPrime为0（假），则lngN不是质数。

编写具有以下规格说明的C程序：

程序使用for循环检查数字的素性。

程序要求用户输入数字N（2≤N≤2 000 000 000），以确定此数字是否为质数。如果用户输入该范围之外的数字N，则程序要求用户重新输入此数字。然后程序检查此数字的素性。如果用户输入0，则程序终止。

代码

以下是使用这些规格说明编写的C程序的代码。在C文件中键入以下文本（程序）并将其保存在文件夹C:\Code中，文件名为prime.c：

编译并执行此程序。此程序的一次运行结果如下所示：

工作原理

LOC 25～30中包含的for循环完成了检查数字的素性的大部分工作。LOC 31～34中的代码显示结果。在此程序中使用具有两层嵌套的do-while循环。只要用户未能在指定范围内输入数字N，内部do-while循环就会将用户保持在循环内。只要用户想要检查新数字的素性，外部do-while循环就会将用户保持在循环内。内部do-while循环增加了此程序的稳健性。请注意LOC 35，此处摘录以供你快速参考：

这似乎是一个无限循环，因为括号中没有比较语句。但是，在LOC 18中提供了终止循环的规定，这里也摘录以供你快速参考：

当lngN的值为零时，此循环的执行将成功终止。

库函数ceil()和sqrt()在LOC 24中使用，这里也摘录以供你快速参考：

库函数ceil()和sqrt()是数学函数，这就是通过LOC 2将头文件math.h包含在这个程序中的原因。术语sqrt代表“平方根”，术语ceil代表“上取整”，这反过来意味着上限。以下是使用库函数sqrt()的语句的通用语法：

这里，dblY是一个表达式，其计算结果为double类型的常量，而dblX是double类型的变量。函数sqrt()计算dblY的平方根并返回结果，该结果赋值给变量dblX。

函数ceil()将double值（作为参数传递）转换为较大的最接近的整数值并返回结果。以下是使用函数ceil()的语句的通用语法：

这里，dblY是一个表达式，其计算结果为double类型的常量，而dblX是一个double变量。