题解 | 几乎是质数

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<ll, ll> P;
#define x first
#define y second
#define int long long
#define i128 __int128

const int mod = 1e9 + 7;
const int MOD = 998244353;

const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};

ll ksm(ll a, ll b, ll p) {
    ll ans = 1;
    a %= p;
    while (b) {
        if (b & 1) ans = (ans * a) % p;
        b >>= 1;
        a = (a * a) % p;
    }
    return ans % p;
}

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    std::uniform_int_distribution<int> distribution(l, r);
    return distribution(rng);
}
bool isprime(int x)
{
    if(x==1)return false ;
    for(int i = 2;i*i <= x;i++)
    {
        if(x%i==0)return false;
    }
    return true;
}
bool ok(int x)
{
    int cnt = 0;
    
        for(int i = 2;i * i<= x;i++){
            if(x%i==0){
                cnt++;
                if(cnt>2)return false;
                while(x%i==0){
                    x/=i;
                }
            }
        }
        if(x>1)cnt++;
        return cnt == 2;
}

signed main () {
    // init(minp, primes, m); // primes
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    // init();
    int t;
    cin>>t;
    int cnt = 0;
    for(int i = 1;i <= t;i++)
    {
        if(ok(i))cnt++;
    }
    cout<<cnt;
    return 0;
}