埃筛

#include<stdio.h>
#include<math.h>

const int N = 1000010;
bool ispri[N] = {true, true};

int cnt = 0;
int n;
void es(){
    int last = sqrt(N + 0.5);
    for(int i = 2; i <= last; i++){
        if(!ispri[i]){
            for(int j = i * i; j <= N; j += i)
                ispri[j] = true;
        }
    }    
}

int main()
{
    es();

    scanf("%d", &n);

    for(int i = 2; i <= n; i++) if(!ispri[i]) cnt++;

    printf("%d\n", cnt);

    return 0;
}

线性筛

#include<stdio.h>
#include<math.h>

const int N = 1000010;
bool ispri[N] = {true, true};
int pri[N];
int cnt = 0;
int num = 0;
int n;
void xs(){
    for(int i = 2; i < N; i++){
        if(!ispri[i]) pri[cnt++] = i;
        for(int j = 0; j < cnt && 1ll * i * pri[j] <= N; j++){
            ispri[i * pri[j]] = true;
            if(i % pri[j] == 0) break;
        }
    }
}

int main()
{
    xs();

    scanf("%d", &n);

    for(int i = 2; i <= n; i++) if(!ispri[i]) num++;

    printf("%d\n", num);

    return 0;
}