一旦对程序进行了优化，就要重新测试程序，以便因优化考虑不周带来新的问题。当然，有些局部优化也可能影响全局的效果。总之，不能认为只是局部优化就无需测试验证。
【例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 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 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 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 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 13
17 19 23 29 31
37 41 43 47 53
59 61 67 71 73
79 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，所以这个判别是不起作用的，可以删除。