算法1

(线性筛) $O(n)$

参考文献

竹林正在青大佬的题解

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=100000010;
int a[N],n,cnt;
bool st[N];
//朴素筛 O(nlogn)
void get_prime1(int n){
    int i,j;
    for (i=2;i<=n;i++){
        if (!st[i]) a[cnt++]=i;
        for (j=i+i;j<=n;j+=i) st[j]=1;
    }
}
//埃氏筛 O(nloglogn)
void get_prime2(int n){
    int i,j;
    for (i=2;i<=n;i++){
        if (!st[i]) {
            a[cnt++]=i;
            for (j=i+i;j<=n;j+=i) st[j]=1;  
        }
        //if (cnt==100017) return ;
    }
}
//线性筛O(n) 
void get_prime3(int n){
    int i,j;
    for (i=2;i<=n;i++){
        if (!st[i]) a[cnt++]=i;
//核心思想 一个合数 其最小质因子必定为质数 
//算法核心：x仅会被其最小质因子筛去 
        for (j=0;a[j]<=n/i;j++){//左边的式子是a[j]*i<=n的变形 防止st数组越界而已 
//此循环会筛掉i与当前所有质数的积 若发现i已经被筛去(i%a[j]==0) 则break
//如此才能做到每个合数只筛一次
//若i为质数则最后一次循环筛去的是i的平方
//若i为合数 则必定会break 原理见上方的核心思想和算法核心 
            st[a[j]*i]=1;
            if (i%a[j]==0) break;
//1.i%aj == 0, aj定为i最小质因子，aj也定为aj*i最小质因子
//2.i%aj != 0, aj定小于i的所有质因子，所以aj也为aj*i最小质因子
        }
    }
}

int main (){
    scanf ("%d",&n);
    get_prime3(n);
    printf ("%d\n",cnt);
}