一旦對程序進行了優化，就要重新測試程序，以便因優化考慮不周帶來新的問題。當然，有些局部優化也可能影響全局的效果。總之，不能認為只是局部優化就無需測試驗證。
【例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，所以這個判別是不起作用的，可以刪除。