Problem:https://www.spoj.com/problems/NGIRL/
(Ubuntu Pastebin)
Why I am getting WA? I can’t figure out the case that fails to produce a correct answer?
Code:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e5 + 10;
vector v(N, 0);
vector prime;
void sieve()
{
v[0] = v[1] = 1;
for (int i = 2; i * i <= N; i++)
{
if (v[i] == 0)
{
for (int j = i * i; j <= N; j += i)
{
v[j] = 1;
}
}
}
for (int i = 2; i <= N; i++)
{
if (v[i] == 0)
{
prime.push_back(i);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
sieve();
int t;
cin >> t;
while (t--)
{
int n, k,like=0,choice=0;
cin >> n >> k;
int m = n;
n = sqrt(n);
auto it = upper_bound(prime.begin(), prime.end(), n);
it--;
choice = it - prime.begin() + 1;
cout << choice << " ";
if(k<=m){
k = sqrt(k);
it = upper_bound(prime.begin(), prime.end(), k);
it--;
ll x = it - prime.begin() + 1;
like = choice - x;
}
cout << like <<"\n";
}
return 0;
}