最近新开了一个栏目，打算记一些常见问题的算法，以后说不定有用到可以套用一些。

质数的定义

质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。

这次我们的例题是：

求n以内的质数。（其中 n是传入的参数）。

这里我们介绍三种常见方法：

1.完全遍历法：

这种算法比较基本，对于每个数n，将n依次从2除到n，然后对余数进行比较，如果余数是0，则除得尽，如果不是0则除不尽，按照质数的定义，只有1和他本身能成为因数也就是除得尽，所以只有除得尽的数不大于两个时，才能是质数。

算法实现：

int n;

int count=0;

cin>>n;

for（int i =2;i<=n;i++）{ //i从2开始相应了质数定义中的第一句话。

for(int j = 1;j<=n;j++) //从1开始响应了质数定义中“除了1和其本身外没有其他因数的特点”

if(i&j==0)

count++;

if(count ==2)

cout<

}

这种算法的好处是符合大多数人的第一反应，和定义契合得比较好，也比较省空间，但问题是假如我这里n输入了1000000+时，这个运算时间是非常长的，其算法复杂度高达1*10^12,小数据可以用遇到大数据就很难实现高效了。

开根号遍历法

仔细分析算法我们会发现，其实在做除法运算时不需要除每一个数，只要除到根号n即可。这是因为当除数大于根号n时，其结果肯定是小于根号n的（可以用反证法证明），假如此时能除得尽，那么该种可能早就在小于根号n的遍历中被排除掉了，就没有意义了。这样就减小了一部分算法复杂度。

算法实现：

int n;

int count=0;

cin>>n;

for（int i =2;i<=n;i++）{ //i从2开始相应了质数定义中的第一句话。

for(int j = 1;j<=sqrt(n);j++) //从1开始

if(i&j==0)

{count++;

if(count==2)

break;

}

if(count ==1)

cout<

}

筛选法

筛选法的核心是牺牲内存换速度，因为其不通过遍历来表达一列数而是直接通过数组来表达。用静态的bool量去变现数的状态。

其核心流程为：

定义一个bool数组，其下标为我们要判断的数，其值为true。表示初始阶段所有数都假定是素数。开始对这个数组进行筛选（及把值改为false），实现把因数含有2的所有数筛掉，把因数含有3的数筛掉，把因数含有5的数筛掉…一直筛选到只剩下素数为止。

这种方法的效率非常高，对于大小超过10万的数据非常好用，但是对于数据量为千万级的数来说，普通定义的数组是不够好用的，在实际调试中我们可以发现，当数据大于800万时，定义普通数组会报错。这时我们可以利用STL标准库中来定义数组。

#include

using namespace std;

vector sieve(int n); //函数声明,求n以内的质数

int main(int argc, char const *argv[])

{

int n;

cin >> n;

vector ans = sieve(n);

cout << ans.size() << endl;

for (int i = 0; i < ans.size(); i++) {

cout << ans[i];

if (i < ans.size() - 1)cout << " ";

}

cout << endl;

return 0;

}

#include

vectorsieve(int n){

int j;

vector all;

vector shuju;

for (int k = 0;k<=n;k++)

all.push_back(true) ;

for(j=2;j<=sqrt(n);j++){

for(int i=2;i*j<=n;i++)

all[i*j] = false;

}

for(int i = 2;i<=n;i++){

if(all[i])

shuju.push_back(i);

}

return shuju;

}

这种方法运算效率非常高，特别是在十万级以上的数中，其牺牲掉的内存不多，但对速度的提升确实是非常显著的。