# CHEFMGX - Editorial

Setter: Shivansh Kaushal
Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi

EASY

## PREREQUISITES:

Sieve of Eratosthenes

## PROBLEM:

Chef needs to go from X to Y. For this he can consider the following two operations:

Suppose chef is at location C. Now he can

• Go from C to C+1 in one step

• Go from C to C+2 in one step if C+2 is prime.

We need to find the minimum number of steps to go from X to Y.

## EXPLANATION:

• If the move C to C+2 is possible, we must always prefer this rather than going from C \rightarrow C+1 \rightarrow C+2 because it always saves us one step.

• Let us find the number of prime numbers P \leq Y for which P-2 \geq X. Let this value be tot.

• Whenever we want to go to such P we will prefer the second operation, i.e going from P-2 to P directly using one step.

• Therefore, our final answer will be Y-X-tot .

• We can precompute the number of primes from 1 to N using the sieve method. From this information, we can easily calculate the number of primes in a range in O(1) time.

## TIME COMPLEXITY:

O(N \log \log N) where N =10^7 for performing sieve.

## SOLUTION:

Editorialist's solution
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e7;
bool prime[MAXN + 5];
int tot_primes_till[MAXN + 5];

void sieve()
{
int n = MAXN;
fill(begin(prime), end(prime), true);
prime[0] = prime[1] = false;

for (int i = 2; i <= n; i++)
{
tot_primes_till[i] = tot_primes_till[i - 1];

if (!prime[i])
continue;

tot_primes_till[i]++;

for (int j = 2 * i; j <= n; j += i)
{
prime[j] = false;
}
}
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

sieve();
int tests;
cin >> tests;

while (tests--)
{
int X, Y;
cin >> X >> Y;

int ans = Y - X - (tot_primes_till[Y] - tot_primes_till[X + 1]);

cout << ans << "\n";
}
}


Setter's solution
#include<bits/stdc++.h>
using namespace std;

#define ll long long int

ll prime[10000004] = {0};

void sieve()
{
ll n=10000004;
prime[1]=1;
for(ll i=2;i<=n;i++)
{
for(int j=2;i*j<=n;j++)
{
prime[j*i]=1;
}
}
}

ll prime_in_range[10000004];

// Function to count primes in range.
void count_prime()
{
prime_in_range[0] = 0;
prime_in_range[1] = 0;
prime_in_range[2] = 1;

for(int i=3 ; i<=10000004 ; i++)
{
if(prime[i] == 0)  // if the number if prime
{
prime_in_range[i] = prime_in_range[i-1] + 1;
}
else
{
prime_in_range[i] = prime_in_range[i-1];
}
}
}

int main()
{
// freopen("input2.txt","r",stdin);
// freopen("output2.txt","w",stdout);
ios::sync_with_stdio(false);
cin.tie(NULL);

ll t;
cin>>t;

sieve();
count_prime();

while(t--)
{
ll x,y;
cin>>x>>y;

cout << y - x - (prime_in_range[y]-prime_in_range[x+1])<<"\n";
}
}


Tester's solution
#include <bits/stdc++.h>
using namespace std;
#define N 10000001
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<int> p(N);
for (int i = 2; i < N; i++)
{
p[i] = 1 - p[i];
if (p[i])
{
for (int j = 2 * i; j < N; j += i)
{
p[j] = 1;
}
}
p[i] += p[i - 1];
}
int t;
cin >> t;
while (t--)
{
int x, y;
cin >> x >> y;
cout << y - x - p[y] + p[x + 1] << "\n";
}
return 0;
}


Please comment below if you have any questions, alternate solutions, or suggestions.

4 Likes

Need python solution.

2 Likes

Why My Solution Giving TLE In Second Testcase

Here is my code:

#include<bits/stdc++.h>
#define flash ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long int
#define md 10000001
using namespace std;

bool prime[md];
void SieveOfEratosthenes()
{
memset(prime, true, sizeof(prime));
for (int p=2;p*p<=md;p++)
{
if (prime[p] == true)
{
for (int i = p * p; i <= md; i += p)
prime[i] = false;
}
}
}

int rec(int x,int y){
if(x>=y)
return 0;
if(prime[x+2])
return 1+rec(x+2,y);
else
return 1+rec(x+1,y);
}

void solve(){
int x,y;
cin>>x>>y;
int cnt=rec(x,y);
cout<<cnt<<"\n";
}

int32_t main(){
flash;
SieveOfEratosthenes();
int tc;
cin>>tc;
while(tc–)
{
solve();
}
}

Try using “long long” instead of “int” in the for loops in the function “SieveOfEratosthenes()”.
For large value of p (like 1e5), storing p*p as integer will cause integer overflow.

Can Anyone help me to optimize my logic

Solution Link : Solution: 52762183 | CodeChef

That’s a baseless advice. He has written p * p <= md, where md = 10000001. This will not cause overflow in any case.

1 Like

Yours is an O(T\times (Y - X)) Solution which will timeout for given Constraints. You can go through the editorial for a better understanding.

1 Like

Declaring a global array of size 1e7 was causing some runtime error in my PC. What can be the reasons and how to correct that . I am using c++.

In the Setter’s solution, the size of Array is around 10^6, but the constraints mentioned were N\le10^7. Is it that the setter’s solution was provided for a reference, or the tests were generated based on this solution?

If you’re using Linux, you can refer to this.

Edit: There’s a Codeforces topic on this.

I have already defined int as long long globally (see code line number 3).

Ok thanks .
Is this approach correct for smaller constraints?

It would pass for the following constraints.

1\le (T\times (Y - X))\le10^7.

Like this: 1\le T\le10^4 and 1\le X\lt Y\le10^3
or this: 1\le T\le10^6 and 1\le X\lt Y\le10
or even this: 1\le T\le 10 and 1\le M\lt N \le 10^6.

1 Like

Can someone clear my doubt? Is the while loop giving me TLE or the sieve?

Solution: 52710238 | CodeChef

The time Complexity of your code is O(Y - X) per test case. You should do it in O(1) per test case.

1 Like

Hey previously the contraints were 10^6 but later increased to 10^7. Thanks for pointing this out. I have updated the setter’s solution.

1 Like

Consider the following lines of code.

int INF = 1000000007;

int a = 999999;
int b = 999999;

int product = a*b;

if(product <= INF){
cout << "a*b is less than or equal to INF";
}else{
cout << "a*b is greater than INF";
}


If we calculate a*b with a calculator, it will be 999998000001.

So, we can expect the program to print “a*b is greater than INF”, as with no doubt 999998000001 is greater than 1000000007.

But the above program actually prints “a*b is less than or equal to INF”.

It is because, “a” and “b” are declared as integers, so “a*b”, will also be stored as an integer but their product “999998000001” exceeds the limit of integers, and therefore cause integer overflow.

So instead of “999998000001”, product will store “-729379967”.

This is what I meant, when I said “storing p*p as integer will cause integer overflow”.

But he has defined “int” as “long long int” in his code, so, this integer overflow is out of question.

1 Like