输出样例：
4
朴素筛法
把从2~n中的从小到大一次删掉每个数的倍数
#include #include using namespace std;const int N= 1000010;int primes[N], cnt;// primes[]存储所有素数bool st[N];// st[x]存储x是否被筛掉void get_primes(int n){for (int i = 2; i <= n; i ++ ){if (st[i]) continue;primes[cnt ++ ] = i;for (int j = i + i; j <= n; j += i)st[j] = true;}}int main(){int n;cin >> n;get_primes(n);cout << cnt << endl;return 0;}
埃氏筛法
只把质数的倍数删掉
#include #include using namespace std;const int N= 1000010;int primes[N], cnt;// primes[]存储所有素数bool st[N];// st[x]存储x是否被筛掉void get_primes(int n){for (int i = 2; i <= n; i ++ ){if (!st[i]) {primes[cnt ++ ] = i;for (int j = i + i; j <= n; j += i)//将i的所有倍数删掉（循环放在里面）st[j] = true;}}}int main(){int n;cin >> n;get_primes(n);cout << cnt << endl;return 0;}
线性筛法
【c++质数——数学知识】//算法核心：x仅会被其最小质因子筛去#include #include using namespace std;const int N= 1000010;int primes[N], cnt; // primes[]存储所有素数bool st[N];// st[x]存储x是否被筛掉void get_primes(int n){for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[cnt ++ ] = i;//假设primes[0]为n最小的质因子,i为最大的因数，//易知若primes[i]中i>0,则会进入循环后产生多余的标记 。for (int j = 0; primes[j] <= n / i; j ++ )//对于任意一个合数x，假设pj为x最小质因子，当i> n;get_primes(n);cout << cnt << endl;return 0;}
