质数筛

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, primes[N];
int get_prime(int u)
{
    int cnt = 0;
    memset(primes, true, sizeof primes);
    primes[1] = false;
    for(int i = 2; i <= u; i ++ )
    {
        if(primes[i])
        {
            cnt ++ ;
            for(int j = i; j <= u / i; j ++ )
                primes[j * i] = false;
        }
    }
    return cnt;
}
int main()
{
    cin >> n;
    cout << get_prime(n) << endl;


    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, primes[N];
int get_prime(int u)
{
    memset(primes, true, sizeof primes);
    primes[1] = false;
    int cnt = 0, q[N];
    for(int i = 2; i <= u; i ++ )
    {
        if(primes[i]) q[cnt ++ ] = i;
        for(int j = 0; q[j] <= u / i; j ++ )
        {
            primes[q[j] * i] = false;
            if(i % q[j] == 0) break;
        }
    }
    return cnt;
}
int main()
{
    cin >> n;
    cout << get_prime(n) << endl;


    return 0;
}