一旦对程序进行了优化，就要重新测试程序，以便因优化考虑不周带来新的问题。当然，有些局部优化也可能影响全局的效果。总之，不能认为只是局部优化就无需测试验证。
【例25.3】将1~100内的所有素数存入数组，然后输出全部素数、最大素数和素数数量。
“素数”，又称“质数”，是指除1和其自身之外，没有其他约数的正整数。如2，3，5，7，11，13，17，19，23，29等。2是最小的质数，也是唯一的偶质数。与素数对应的是“合数”，合数是除1和其自身之外，仍有其他约数的正整数。并且规定0既不是质数，也不是合数。数字1很特殊，也不称为质数。著名的高斯“唯一分解定理”是说任何一个整数都可以写成一串质数相乘的积。
根据质数的定义，可以编写出满足要求的程序。
#include <stdio.h>int main（）{ int i=0， j=-1， a[50]； int num=100； for（num=1；num<=100；num++） { for（i=2；i<=num；i++） { if（num % i == 0） break； } if（i == num） { ++j； a[j] = num； } } for（i=1； i<=j+1 ；i++） { printf（/"%2d /"， a[i-1]）； if（ i % 5 == 0 ） printf（/"n/"）； } printf（/"n最大素数是%dn/"，a[j]）； printf（/"有素数%d个n/"，j+1）； return 0；} 程序运行结果如下：
2 3 5 7 1113 17 19 23 2931 37 41 43 4753 59 61 67 7173 79 83 89 97最大素数是97有素数25个
【分析】程序中有许多是无效的运算，第1个循环的循环次数至少可以减少一半，显然，第2个循环语句的循环次数至少也可以与第1个循环一样减少一半，再细推敲，将该数的平方根取整作为循环次数即可。
//优化的程序#include <stdio.h>#include <math.h>int main（）{ int i=0， j=-1， a[50]； int num=0， temp=0； for（num=1； num<=100； num += 2） //步长为2，剔除偶数 { temp=（int）sqrt（num）； //循环限制为其平方根取整 for（i=2； i<=temp； i++） { if（num % i == 0） //排除合数 break； } if（i == temp+1） { ++j； //质数计数 a[j] = num； //将质数存入数组 } } //输出结果 for（i=1； i<=j+1 ；i++） { printf（/"%2d /"， a[i-1]）； if（ i % 5 == 0 ） printf（/"n/"）； } printf（/"n最大素数是%dn/"，a[j]）； printf（/"有素数%d个n/"，j+1）； return 0；} 程序运行结果如下：
1 3 5 7 1113 17 19 23 2931 37 41 43 4753 59 61 67 7173 79 83 89 97最大素数是97有素数25个
如果只是求素数数量和最大素数，优化成功。但程序要求输出素数，则就存在错误了。从程序输出结果可见，少了素数2，多了数字1。
由此可见，在优化时，正确的做法是每修改一处都要立即进行验证。一定不要怕麻烦，就像排错一样，每改一处必须从头测试。
现在是多次优化的结果，产生错误的地方就应从头开始验证了。
程序从引入temp变量入手，第1个循环的步长可以先修改，然后使用temp变量。
//第1次优化及其运行结果#include <stdio.h>#include <math.h>int main（）{ int i=0， j=-1， a[50]； int num=0， temp=0； for（num=1； num<=100； num += 2） { temp=num-1； for（i=2；i<=temp；i++） { if（num % i == 0） break； } if（i == temp+1） { ++j； a[j] = num； } } for（i=1； i<=j+1 ；i++） { printf（/"%2d /"， a[i-1]）； if（ i % 5 == 0 ） printf（/"n/"）； } printf（/"n最大素数是%dn/"，a[j]）； printf（/"有素数%d个n/"，j+1）； return 0；}3 5 7 11 1317 19 23 29 3137 41 43 47 5359 61 67 71 7379 83 89 97最大素数是97有素数24个 从输出结果可知，少了一个素数2。与上一个优化相比，那个程序是少了素数2，多了数字1。由此可推知多的数字1是由取平方根引起的。分析一下可知，num为1和2时，temp均为1，由此造成多了个1。针对这两个问题采取相应对策即可。
//正确优化的程序#include <stdio.h>#include <math.h>int main（）{ int i=0， j=0， a[50]； int num=100，temp=0； a[0]=2； //找回2 for（num=1；num<=100； num += 2） { temp=（int）sqrt（num）； for（i=2；i<=temp；i++） { if（num % i == 0） break； } if（i == temp+1） { if（ num ！= 1 ） //排除1 { ++j； a[j] = num； } } } for（i=1； i<=j+1 ；i++） { printf（/"%2d /"， a[i-1]）； if（ i % 5 == 0 ） printf（/"n/"）； } printf（/"n最大素数是%dn/"，a[j]）； printf（/"有素数%d个n/"，j+1）； return 0；} 这个算法每次都要调用sqrt函数，花费时间较多。下面的优化减少了调用次数，改善了程序性能。因为增加了prime函数，结构化也更好些。
//减少开平方次数的算法#include <stdio.h>#include <math.h>int prime（int num）；int main（）{ int i=0， j=0， a[50]； int num=100； for（num=1； num<=100； num = num+2） { if （ num == 1 ） { a[j]=2； j++； continue； } if （ prime（num） ） { a[j] = num； ++j； } } for（i=1； i<j+1 ；i++） { printf（/"%2d /"， a[i-1]）； if（ i % 5 == 0 ） printf（/"n/"）； } printf（/"n最大素数是%dn/"，a[j-1]）； printf（/"有素数%d个n/"，j）； return 0；}int prime（int num）{ int temp=0， i=0； if（num % 2 == 0） //多余，见下节 return （ num == 2）； if（num % 3 == 0） return （ num == 3）； if（num % 5 == 0） return （ num == 5）； temp = （int）sqrt（num）； for（i=7； i<=temp； i=i+2） if（num % i == 0） return 0； return 1；} 如果把数组改为a[200]，num=1000，则得到最大素数是997，有素数168个。第1个素数是2，全部正确。
如果使用乘法代替开平方，速度会更快。下面是求1~1000的质数的程序。
//使用乘法的算法#include <stdio.h>#include <math.h>int prime（int num）；int main（ ）{ int i=0， j=0， a[200]； int num=100； for（num=1； num<=1000； num = num+2） { if （ num == 1 ） { a[j]=2； j++； continue； } if （ prime（num） ） { a[j] = num； ++j； } } for（i=1； i<j+1 ；i++） { printf（/"%2d /"， a[i-1]）； if（ i % 5 == 0 ） printf（/"n/"）； } printf（/"n最大素数是%dn/"，a[j-1]）； printf（/"有素数%d个n/"，j）； return 0；}int prime（int num）{ int temp = 0， i = 0； if（num % 2 == 0） //多余 return （ num == 2）； if（num % 3 == 0） return （ num == 3）； if（num % 5 == 0） return （ num == 5）； for（i=7； i*i<=num； i=i+2） if（num % i == 0） return 0； return 1；} 由此可见，不同算法的效率大不一样，优化时一定要仔细考虑，选取效率高的算法。这也是为什么总是建议先编写一个正确求解的程序，在编写过程中不要急于优化，要把注意力集中在正确求解，而把优化放在后面。如上所示，后面两种算法将判定质数提取出来作为一个函数，在函数里集中解决算法效率。
优化时出现漏解和多解也是正常的事情，关键是分析如何补救。其实，上面的程序含有多余的语句。
if（num % 2 == 0） return （ num == 2）；
的目的是使num=2时，不会被丢掉（2是质数）。其实在主程序里，循环取值是奇数，而且已经补上a[0]=2，所以这个判别是不起作用的，可以删除。