题解

方法一：

数据范围是1-$10^6$，所以暴力完全可以破解：

#include <iostream>
#include <cmath>
using namespace std;
int m(int i){
    for(int j=2;j<sqrt(i)+2;j++){
        if(i!=j and i%j==0){
            return 0;
        }
    }return 1;
}
int main(){
    int a;
    cin >> a;
    int num=0;
    for(int i=2;i<=a;i++){
        num+=m(i);
    }cout <<num;
    return 0;
}

时间复杂度：$O(n\sqrt{n})$

方法二：

直接用埃氏筛法筛一遍，再用$O(n)$的复杂度统计质数即可:

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a;    
    cin >> a;
    int sz[1000005]={};
    sz[1]=1;
    int num=0;
    for(int i=1;i*i<=a;i++){
        if(sz[i]==0){
            
            for(int j=2*i;j<=a;j+=i){
                sz[j]=1;
            }
        }
    }
    for(int i=1;i<=a;i++){
        if(sz[i]==0){
            num++;
        }
    }
    cout << num;
    return 0;
} 

时间复杂度：$O(2n \log \log n)$