素数指的是因子只有1和本身的数（1不是素数），求解素数在数学上应用非常广泛，而求解n以内的素数也是我们编程时常遇到的问题，在这个问题上，筛选法求解素数运行得非常快。下面首先介绍如何判断一个是不是素数，然后介绍用普通方法求n以内的素数，接着是筛选法求n以内的素数，最后是两种算法的运行时间比较
判断一个数是不是素数
算法思想：判断小于等于一个数的平方的所有大于1的整数是不是能整除这个数，如果能，则表明这个数不是素数；反之，则是素数。
){int m = sqrt(value);if (value < 2) return false;for (int i = 2; i <= m; i++){if ((value%i)==0){return false;}}return true;}普通方法求解n以内的素数
算法思想：声明一个n大小的bool数组，初始值为false，然后从2开始判断一个数是否为素数，若是，则将其的布尔值定为true
//普通法求素数bool* putong(int n){bool* value = new bool[n];for (int i = 0; i < n; i++)value[i] = false;for (int i = 2; i < n; i++){if (isPlain(i)){value[i] = true;}}return value;}筛选法求n以内的素数
算法思想：找出小于等于n的开方的素数，然后将n内所有这些素数的倍数统统去掉，剩下的数就都是素数，也是通过布尔数组实现
//筛选法求素数bool* shuaixuan(int n){bool* value = new bool[n];for (int i = 0; i<n; i++)value[i] = true;value[0] = false;value[1] = false;for (int i = 2; i <= sqrt(n); i++){if (value[i] && isPlain(i)){int c = 2;int j = i*c;while (j < n){value[j] = false;j = i*c++;}}}return value;}完整代码及运行结果
下述代码分别调用了普通方法和筛选法，可循环输入n（按Ctrl + C结束），以供不同数据的测试，，后面附了一张运行测试的结果图
#include <iostream>using namespace std;isPlain(int value){int m = sqrt(value);if (value < 2) return false;for (int i = 2; i <= m; i++){if ((value%i)==0){return false;}}return true;}//普通法求素数bool* putong(int n){bool* value = new bool[n];for (int i = 0; i < n; i++)value[i] = false;for (int i = 2; i < n; i++){if (isPlain(i)){value[i] = true;}}return value;}//筛选法求素数bool* shuaixuan(int n){bool* value = new bool[n];for (int i = 0; i<n; i++)value[i] = true;value[0] = false;value[1] = false;for (int i = 2; i <= sqrt(n); i++){if (value[i] && isPlain(i)){int c = 2;int j = i*c;while (j < n){value[j] = false;j = i*c++;}}}return value;}int main(){int n;while (cin >> n){int start = clock();bool* value1 = putong(n);int end = clock();cout << “普通方法：” << end – start << endl;start = clock();bool* value2 = shuaixuan(n);end = clock();cout << “筛选法：” << end – start << endl;delete[] value1;value1 = NULL;delete[] value2;value2 = NULL;}_getch();}
从图中可看出，n越大，筛选法对普通方法的性能就越好。
耿耿于怀着过去和忐忑不安着未来的人，也常常挥霍无度着现在。
