[开场白]
这个系列的文章本来是发表在我们学院的级队报上的，觉得写了就别浪费，于是贴到这里，属于自娱自乐，这个系列的主要是给C++初学者的，没有什么高深的理论和技术。主要谈谈一些常用算法，编程原则，编码技巧，编程感想等等。
[本期问题]
求1~10000内的所有质数
[分析1：]
分析题目后，我们可以用一个变量为i的for 循环来历遍1~10000所有的数，在循环体内判断当前的i是不是质数。由质数定义知：只能被1和它本身整除的数为质数（不包括1）。我们用bool型变量isPrime来记录当前的数是不是质数，在循环内部用一层值从2变到i ,变量为j的for 循环来判断：看i%j的结果是不是0,若是0则说明i为合数；i一定的时候，若所有的i%j都不等于0,则说明它是质数。
按照上面的描述，我们可以写出一个程序，参考程序见《c++基础教程》第443页~第444页。书中的程序正确地解决了问题，但它是最快的么？不！
在初等数论中有这样的定理：合数n若它的两个因数相乘得n,则其中较小的一个因数不大于√n ; 所以我们可以把for(j=2;j<=i/2;j++)改成for(j=2;j<=(int)sqrt(i);j++) (当然，你需要包含头文件<cmath>)。
还可以再快么？当然可以。让我们分析一下源代码，当i=10000时,j从2开始递增。当j=2时（i%j）==0为true。所以isPrime会被赋值为false。这说明10000已经不是质数了，但是计算机仍然会“尽职尽责”的继续从3判断到100，这些工作是毫无用处的（或许有，那就是让你的电脑做运动）。因此，在if((i%j)==0)成立时执行的语句中再加一句：break;让程序直接判断下一个数。
我们还知道，除了2以外的所用数都是合数，因此，我们可以用i+=2来代替i++。以下是修改后的代码：
#include <iostream>
#include <cmath>
using namespace std;
const MAX=10000; //参见后面的解释1
bool isPrime; //记录是不是质数
int i,j; //循环变量
int main(){
int t; //临时变量
cout<<"2 ";
//下面的循环是历遍从3到10000的奇数
for (i=3 ; i <= MAX ; i+=2;){
isPrime=true;
t=(int)sqrt(i); //参见解释2
//下面这个循环体是用来判断i是不是质数
for (j=2 ; j<=t ; j++){
if (0==(i%j)) { //参见解释3
isPrime=false;
break;
}
}
if (isPrime) {
cout<<i<<" ";
}
}
return 0;
}
以下解释关于编程技巧和习惯的：
1. 将10000定义成常量，这是个好主意，将程序中多次，重复出现的数定义成常量。这样，当你有一天忽然想要求100000以内的质数时，只需要修改一处：常量的定义。
2. 将for ( j = 2 ; j <=（int) sqrt (i) ; j++ ){…}分成了两句：t=(int)sqrt(i);for (j=2 ; j<=t ; j++){…}有什么好处？在j从2变到√i中的每次判断(int)sqrt(i)一直是一个定值，但电脑不知道，他只会做你让他做的事：在每一次j++ 后，对i进行开方，对整个程序来说，这是个很大的运算量，所以把它放到循环体前，只有在改变i值时i开方才运算一次。
3． 0==(i%j)，相信不少的同学喜欢写成(i%j)==0，并顺手写成=，这是一个常见的易忽略的而又会在运行时发作，调试时让你找不出来而抓狂的错误。如果你有以上习惯，那么你可能会写出if (k=1)…，而结果是条件永真！所以，把常量写在==左边是一个我个人比较推荐的（不是强迫的）写法，当你不小心把==写成了=时,编译器会给你一个“non-lvalue in assignment”，然后你只需要改正错误。把找出隐藏错误的能力交给编译器，让自己酸疼的手，发糊的眼休息，应该是每一个编程的人的愿望。
[分析2：]
筛选法，就是想用筛子筛东西一样，比如豆子和沙子在一起，由于沙子粒小，豆子粒大， 于是我们就取网眼大小适合的筛子，筛取沙子而留下豆子，这就是筛选法。待处理的沙和豆的混合物即待处理的元素集合，要筛取得沙子既不符合条件的元素，留下的豆子即合条件的元素，而筛选的工具筛子就是筛选的条件。若不合条件的元素（或集合）容易求得，而确定的范围也有限，则可用筛选法求解。
筛选法在求某自然数范围的质数时有一个著名的方法叫做Eratosthenes筛法，这种方法大致如下：例如，我们要找出1~100的全部质数，1，不是质数当然划去，在2到100中划去2的倍数（不包括2），再划去3的倍数（不包括3），（4被划去）再划去5的倍数……，直到划去不超过10的倍数，剩下的就是质数。
上述算法可以表达如下：
1．[初始化]建立2到MAX的一个数表；
2．[置ip为2],把2赋给ip,准备划去ip的倍数；
3．[ip>√n?]若ip>√n,转到6；
4．[划去倍数]在数表中划去ip的倍数；
5．[找下一个质数]在ip后继中找第一个未被划去的数作为ip值，然后返回3；
6．[打印]数表中合数以划完，打印并结束。■
以下是筛选算法的c++实现：
#include <iostream>
#include <cmath>
using namespace std;
const MAX=10001;
int ip,kp,t
int a[MAX];
int main(){
for (ip=2;ip<MAX;ip++) {//步骤1
a[ip]=ip;
}
ip = 2;
t=(int)sqrt(MAX); //步骤2
do { //步骤3，4，5
kp = ip;
if( a[kp] > 0){
kp+=ip;
while (kp <= MAX){
a[kp]=0;
kp+=ip;
}
}
ip++;
}while(ip<t);
for (ip=2;ip<=MAX;ip++){//步骤6
if ( a[ip] == ip ){
cout << a[ip] << " ";
}
}
return 0;
}
[结语]
希望大家通过这篇文章，了解遇到一个问题怎么分析，解决，改进。并掌握筛选算法。如果你在阅读本文或者学习c++中发现什么问题，欢迎给我发邮件：[email protected]。
本文地址：http://com.8s8s.com/it/it27901.htm