CPP Code

Nusxalash

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int MOD = 998244353;

int modpow(int a, long long e){
    long long r = 1;
    long long x = a;
    while(e){
        if(e & 1) r = (r * x) % MOD;
        x = (x * x) % MOD;
        e >>= 1;
    }
    return (int)r;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<bool> isPrime(N+1, true);
    if(N >= 0) isPrime[0] = false;
    if(N >= 1) isPrime[1] = false;
    for(int i = 2; i * i <= N; i++){
        if(isPrime[i]){
            for(int j = i * i; j <= N; j += i)
                isPrime[j] = false;
        }
    }

    vector<int> primes;
    for(int i = 2; i <= N; i++) if(isPrime[i]) primes.push_back(i);

    long long cnt = 0;

    for(int p : primes){
        long long t = 1LL * p * p * p;
        if(t <= N) cnt++;
        else break;
    }

    int sz = primes.size();
    for(int i = 0; i < sz; i++){
        for(int j = i + 1; j < sz; j++){
            long long t = 1LL * primes[i] * primes[j];
            if(t <= N) cnt++;
            else break;
        }
    }

    int invN = modpow(N, MOD - 2);
    int ans = (cnt % MOD) * 1LL % MOD * invN % MOD;

    cout << ans;
    return 0;
}