Ý tưởng: chỉ cần đếm xem từ 1 đến căn bậc hai của n có bao nhiêu số nguyên tố 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll nmax = 1e5;
bool check (ll x)
{
    for (ll i = 2; i <= sqrt(x); ++i)
    if (x % i == 0) return false;
    return x > 1;
}
ll n, d = 0;
int main()
{
    freopen("spnum.inp" , "r" , stdin);
    freopen("spnum.out" , "w" , stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (ll i = 2; i <= sqrt(n); ++i)
    {
        if (check(i)) d++;
    }
    cout << d;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int k;
int dem(int n) {
    int d=0;
    for (int i=1;i<=sqrt(n);i++) {
        if (n%i==0) {
            d++;
            if (i!=n/i) {
                d++;
            }
        }
    }
    return d;
}

int main() {
    freopen("spnum.inp" , "r" , stdin);
    freopen("spnum.out" , "w" , stdout);
    cin>>k;
    int sdb=0;
    for (int i=1;i<=k;i++) {
        if (dem(i)==3) {
            sdb++;
        }
    }
    cout<<sdb;
    return 0;
}