思路

原理

用最小质因子筛去合数，保证了每个合数只被筛一次。

核心 ：为什么每个合数只被筛一次？

答：每个合数可以分解为若干个质因数相乘，其中一定存在一个唯一的最小的质因数。
关键代码，这句代码保证了每个合数只会被最小质因数筛去，将时间复杂度降到了线性：

if(i%primes[j] == 0)    break;

证明

1. 首先primes存放的质数是递增的。
2. 当i%pj不为零，pj小于所有i的质因子，并且pj是pj本身的最小质因子。因此，pj是i*pj这个合数的最小质因子。
3. 当i%pj为零，因为pj是从小到大被枚举的，因此pj就是i的最小质因子，并且pj是pj本身的最小质因子。因此，pj是i*pj这个合数的最小质因子。
4. 为什么这个时候要break呢？如果不break，i*primes[j+1]这个合数就会被筛去，但是这个合数的最小质因子不是primes[j+1]。

因为i中含有prime[j],prime[j]比prime[j+1]小，即i=k（某个数）* prime[j].
那么i * prime[j+1]=(k*prime[j]) * prime[j+1]=k * prime[j]

因此，i*primes[j+1]。它的最小质因子不是primes[j+1]，它应该被prime[j]乘上一个不是i的某个数k筛去。所以咯，这个时候应该break，防止后面的合数被重复筛去。也就是说，在满足i%primes[j] == 0这个条件之前以及第一次满足时，pj是pj * i的最小质因子。

代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6 + 10;
int n;
int primes[N],ctn;
bool st[N];

void get_prime(int n){
    for(int i = 2; i<=n; i++){
        if(!st[i])  primes[ctn++]=i;  //从小到大存储质数
        for(int j = 0;primes[j] <= n/i;j++){
            st[i*primes[j]]=true;
            if(i%primes[j] == 0)    break;
        }
    }

}

int main(){

    cin>>n;
    get_prime(n);
    printf("%d",ctn);
    return 0;

}