Can anyone figure out why my code gives WA for 2nd testcase.

@suman_18733097 @ramandeep8421 @ajit123q @shivyyy_21 @mexomerf

I donât understand many things in your code. In your previous code, the implementation of Sieve is lightning fast. What you messed up is the actual solution part.

In the other submission, Sieve is taking too much time. Optimising Sieve should be enough like you did in your previous code.

One thing you can try is to optimise just the Sieve part and submit it. This is based on the fact that your submission that was Accepted has a runtime of 1.94 \text{s}, which is pretty close to 2\text{s}. Using `long long`

should not affect the running time of your solution.

#include <bits/stdc++.h>

using namespace std;

#define ll long long int

#define endl â\nâ

const int m=1e7;

int pri[m+1];

bool isprime[m+1];

int32_t main()

{

```
ios_base::sync_with_stdio(false);
cin.tie(NULL);
isprime[1]=false;
```

for(int i=2;i<=m;i++)

{

```
isprime[i]=true;// first assuming all are prime
```

}

for(int i=2;i<=sqrt(m);i++)

{

```
if(isprime[i])
{
for(int j=i*i;j<=m;j+=i)
{
isprime[j]=false;
}
}
```

}

for(int i=2;i<=m;i++)

{

```
if(isprime[i])
pri[i]=pri[i-1]+1;
else
{
pri[i]=pri[i-1];
}
```

}

```
int t;
cin>>t;
while(t--)
{
int x,y;
cin>>x>>y;
int total;
int ans;
if(x%2==0)
{ total= pri[y]-pri[x+1];
ans=y-x-total;
}
else
{
total=pri[y]-pri[x];
ans=y-x-total;
}
cout<<ans<<endl;
}
```

}

why this is getting wrong

Youâre talking crap. There will not be any integer overflow even if he doesnât write the line `#define int long long int`

.

Reason: The following loop will break as soon as `p * p`

exceeds `md`

. So, the control will not enter the nested `for`

loop.

```
for(int p = 2; p * p <= md; p++)
// md = 10000001
// Max value of p in the loop will be sqrt(md)., viz ~ 3e3
```

Your explanation for the code youâve provided is absolutely correct. But,

The value of `p`

will never exceed `1e4`

, so ** THERE WILL NOT BE ANY OVERFLOW**.

for x odd why we need to do pri[x+1] ?

pri[x] also work??

Thanks again man. I understood my mistake, the thing is I tried out the sieve used in setterâs solution above

I have done the same, i.e use sieve to find primes before hand. but it is still giving TLE

https://www.codechef.com/viewsolution/52743041

How can I improve it ?

Yeah, you are right. I didnât gave much attention to âp*p<=mdâ.

In this case there is not any chance for Integer overflow.

I misunderstood his code.

Thanks for the clarification.

Please someone help me figure out for which testcase does my code goes wrong!!!

@ajit123q I tried running yours and mine code on the following sample TC:

3

1 2

1 3

2 3

Your gave output `1 1 1`

while mine gave output `2 2 2`

, and both are AC, can you explain whatâs going on here? Iâm kind of surprised **how CodeChef accepted my solution, which is actually wrong!**

Your code submission: Solution: 52769423 | CodeChef

My own code submission: Solution: 52769439 | CodeChef

You can try running mine on the sample TC, it will give `2 2 2`

.

can u explain whats u did in last part i mean in if-else condition

The main observation I used is that whenever we have a condition where x is prime or x + 1 is prime or both are prime (in case of 2,3) then the answer is always pre[y]-pre[x] +1, the additional 1 is added because the number of steps to reach x is same as the ones for x+1. the first three cases account for that, this is valid only when x is not 1 because the number of steps to reach 1 is always 0 as clear from the constraints.

I wrote the sequence used this observation and got an AC.You can verify the same by writing a short sequence and trying various endpoints

hey @vrintle For this paricular question the main focus was on second test file , which has 10^6 test cases with X and Y ranging from 1 to 10^7 and its not possible to include every possible test case between 1 to 10^7 within 10^6 range of cases.

here is my python accepted solution.

Link : Solution: 52742643 | CodeChef

i use the same sieve method.