质数的定义
质数（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<<i<<" ";
}
这种算法的好处是符合大多数人的第一反应，和定义契合得比较好，也比较省空间，但问题是假如我这里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<<i<<" ";
}
1
筛选法
筛选法的核心是牺牲内存换速度，因为其不通过遍历来表达一列数而是直接通过数组来表达。用静态的bool量去变现数的状态。
其核心流程为：
定义一个bool数组，其下标为我们要判断的数，其值为true。表示初始阶段所有数都假定是素数。
开始对这个数组进行筛选（及把值改为false），实现把因数含有2的所有数筛掉，把因数含有3的数筛掉，把因数含有5的数筛掉…一直筛选到只剩下素数为止。
这种方法的效率非常高，对于大小超过10万的数据非常好用，但是对于数据量为千万级的数来说，普通定义的数组是不够好用的，在实际调试中我们可以发现，当数据大于800万时，定义普通数组会报错。这时我们可以利用STL标准库中来定义数组。
#include <vector>
using namespace std;
vector<int> sieve(int n); //函数声明,求n以内的质数
int main(int argc, char const *argv[])
{
int n;
cin >> n;
vector<int> 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<math.h>
vector<int>sieve(int n){
int j;
vector<bool> all;
vector<int> 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;
}
