埃氏筛法，快速求出n范围内的素数个数

如果要求一个数是不是素数，只要求2到√n就行，时间复杂度O（√n）。
但是如果判断多个数字是不是素数，如果还用这种方法的话，就会有许多重复判断的。比如，2是素数，那么4，6，8，10等等，全都不是素数了。因此我们只要知道了2是素数后，就把所有2的倍数给去掉，不用在判断了，然后接下来碰到的最小的数字肯定是一个素数，这就是埃氏筛法。

如图，

把2的倍数去掉后，碰到的是3，三肯定是素数，然后把3的倍数去掉后，碰到的是5，5肯定是素数。

代码奉上：

#include <iostream>
#include <cstring> using namespace std;const int max_n = 1000010;
int prime[max_n];    //储存素数的数组
bool is_prime[max_n];   //标记数组，如果是素数标记位trueint sieve(int n)
{int p = 0;//p就代表了有多少个素数 memset(is_prime, true, sizeof(is_prime));is_prime[0] = is_prime[1] = false;for (int i=2; i<=n; i++){if (is_prime[i]){prime[p++] = i;for (int j=2*i; j<=n; j+=i){is_prime[j] = false;      把i的倍数都去掉}}}return p;
}int main()
{int n;cin >> n;cout << sieve(n) << endl;return 0;
}