筛质数

线性筛法 找到最小质因子就可将它的倍数筛去；

算法是线性的时间， O（n）；

以下是代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n, cnt;
int primes[N];
bool st[N];

void get_primes(int x)
{
    for (int i = 2; i <= x; i ++ )
    {
        if(!st[i]) primes[cnt ++] = i;
        for (int j = 0; primes[j] <= x / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }

}

int main()
{
    cin >> n;

    get_primes(n);

    cout << cnt;

    return 0;
}