素数指的是因子仅仅有1和本身的数（1不是素数），求解素数在数学上应用很广泛，而求解n以内的素数也是我们编程时常遇到的问题，在这个问题上，筛选法求解素数执行得很快。以下首先介绍怎样推断一个是不是素数，然后介绍用普通方法求n以内的素数，接着是筛选法求n以内的素数，最后是两种算法的执行时间比較

推断一个数是不是素数

算法思想：推断小于等于一个数的平方的全部大于1的整数是不是能整除这个数，假设能，则表明这个数不是素数；反之，则是素数。

//推断一个数是否为素数 bool 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;}

普通方法求解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（按Ctrl + C结束），以供不同数据的測试，后面附了一张执行測试的结果图

#include 
      
       using namespace std;#include 
       
        #include 
        
         #include 
         
          //推断一个数是否为素数 bool 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){        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越大。筛选法对普通方法的性能就越好。