I passed the subtask but not the full task. I was not going a TLE on main task but a WA. Can someone please help me understand where I went wrong?
My code:
#include <bits/stdc++.h>
using namespace std;
#define for0(i, n) for (ll i = 0; i < (int)(n); i++)
#define for1(i, n) for (ll i = 1; i <= (int)(n); i++)
#define forc(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i)
#define forr0(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define forr1(i, n) for (int i = (int)(n); i >= 1; --i)
#define deb(x) cout << #x << "=" << x << endl
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))
#define tr(x) for(auto it = x.begin(); it != x.end(); it++)
#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define mod 1000000007
#define inf 1e17
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef unsigned long long ull;
typedef vector<pll> vpll;
typedef double ld;
void dk_98() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
const long long MAX_SIZE = 10000002;
vector<long long >isprime(MAX_SIZE , true);
vector<long long >prime;
vector<long long >SPF(MAX_SIZE);
void manipulated_seive(long long N)
{
isprime[0] = isprime[1] = false ;
for (long long int i = 2; i < N ; i++)
{
if (isprime[i])
{
prime.push_back(i);
SPF[i] = i;
}
for (long long int j = 0;
j < (int)prime.size() &&
i * prime[j] < N && prime[j] <= SPF[i];
j++)
{
isprime[i * prime[j]] = false;
SPF[i * prime[j]] = prime[j] ;
}
}
}
void solve() {
ll n; cin >> n;
if (n <= 3) {
cout << n - 1 << "\n";
return;
}
ll j = lower_bound(prime.begin(), prime.end(), n) - prime.begin();
if (prime[j] > n) j--;
ll i = upper_bound(prime.begin(), prime.end(), n / 2) - prime.begin();
//deb(prime[i]); deb(prime[j]);
cout << j - i + 2 << "\n";
}
int main() {
fast;
dk_98();
int t = 1; cin >> t;
manipulated_seive(MAX_SIZE);
while (t--) {
solve();
}
}