Vì 1 số chúng ta chỉ cần kiểm tra 1 lần nên ta dùng thuật toán kiểm tra nguyên tố nhanh để làm

`CODE: C++`

#include<bits/stdc++.h>
#define ll long long
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;
bool nt(ll m)
{
    ll i1;
    if(m==2||m==3)
        return true;
    if(m%2==0||m%3==0||m<2)
        return false;
    for(i1=5; i1<=sqrt(m); i1+=6)
        if(m%i1==0||m%(i1+2)==0)
            return false;
    return true;
}
int main() {
    ios
    ll n;
    cin>>n;
    ll s=0;
    for(int i=1;i<=n;i++)
    {
        if(nt(i))
            s++;
    }
    cout<<s;
    return 0;
}
/*

*   *  *   *    *     *   *       *****    *     ****         ***    ***   ****   *****
**  *  *   *   * *    **  *         *     * *    *   *       *   *  *   *  *   *  *
* * *  *   *  *   *   * * *         *    *   *   *   *       *      *   *  *   *  *
*  **  *****  *****   *  **         *    *****   ****        *      *   *  *   *  ****
*   *  *   *  *   *   *   *         *    *   *   *           *      *   *  *   *  *
*   *  *   *  *   *   *   *         *    *   *   *           *   *  *   *  *   *  *
*   *  *   *  *   *   *   *         *    *   *   *            ***    ***   ****   *****

*/

\begin{array}{c} \color{#db1616}{\texttt{#Khoadang09}} \end{array}
`@`$\texttt{C++: }$

#include <bits/stdc++.h>
#define int long long
#define buff ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
const int MAXZ = 1e6+1;
vector <bool> prime(MAXZ,true);
void solve(){
    for (int i=2;i*i<=MAXZ;i++)
        if (prime[i])
            for (int j=i*i;j<=MAXZ;j+=i)
                prime[j] = false;
}
signed main(){
    buff;
    solve();
    int n; cin >> n;
    int count_prime = 0;
    for (int i=2;i<=n;i++)
        if (prime[i]) count_prime ++;
    cout << count_prime ;
}