CHEFMGX - Editorial

The setter solution in itself giving an RE do check it.

Hey, Setter’s solution is misleading. It says linear Sieve but it’s not.

Nope. I just submitted and it is accepted.

ig the solution might have been updated you can see RE here

Ohk . Thanks dude

Can anyone help!!
Giving TLE on second Task

This is my code:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define int long long int
#define double long double
#define pb push_back
#define fi first
#define se second
#define ins insert
#define endl ‘\n’
#define pbds tree<int,null_type,less,rb_tree_tag,tree_order_statistics_node_update>

const int MOD = 1e9 + 7;

int gcd(int a,int b){
if(b==0) return a;
return gcd(b,a%b);

int lcm(int a,int b){
return ((a/gcd(a,b))*b);

int PowExpo(int a, int b){
int res = 1;
res = (resa)%MOD;
a = (a
return res;

bool IsPrime(int a){
if(a==1) return false;
bool ans = true;
for(int i=2;i<=sqrt((double)a);i++){
ans = false;
return ans;

bool IsPow2(int n){
if(n==0) return false;
return (n&(n-1) ? false:true) ;

int fact(int n){
if(n==0 || n==1){
return 1;
return n*fact(n-1);

int highestPowerof2(int n){
int p = (int)log2(n);
return (int)pow(2, p);

void reverse(string& s){
int i=0;
int j = s.size()-1;
const int MAX = 1e7+1;
vector sieve(MAX, true);
vector primeInRange(MAX,0);

void sieveOfEratosthenes(){
sieve[0] = sieve[1] = false;
for(int i=2;ii<MAX;i++){
for(int j = i
i; j<=MAX ; j+=i){
sieve[j] = false;
primeInRange[2] = 1;
for(int i=3;i<MAX;i++){
primeInRange[i] = primeInRange[i-1]+1;
} else {
primeInRange[i] = primeInRange[i-1];
// for(int i=0;i<20;i++){
// cout << primeInRange[i] << " ";
// }

void solve(){
int l,r; cin >> l >> r;
int count = primeInRange[r]-primeInRange[l+1];
// cout << "count = " << count << endl;
cout << r-l-count << endl;

int32_t main(){
int t=1;
cin >> t;
return 0;

Could somebody please help me find out where I am going wrong, My second test case does not seem to pass. Here is the link to the code: Solution: 52843667 | CodeChef. Any help will be appreciated

Welcome :grin:

1.Firstly, always define the upper bound for the global arrays , so instead of 1e7 , use 1e7 + 7 to avoid memory errors.
2.You are computing the prefix array while precomputing the seive in the outer loop which runs for sqrt(MAXN) , hence only up to sqrt(MAXN) the prefix array is evaluated , and we can assume that the second test case contains input files greater than sqrt(MAXN) which fails , to rectify this you need to compute the prefix array after marking the seive array.
Here is your AC code

1 Like

I understand that it’s not always possible to include every test cases, but this case (in my opinion) was a strong edge case and a basic one, which should have been included.

1 Like

I removed those comments from setters solution. Thanks.

1 Like

Please help me find the error in this solution.
it always passes the first testset , but gives wrong answer in the second testset.
sample testcases are running well too.

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

const int maxx = 1e7;
bool prime[maxx + 5];
ll tot_prime[maxx + 5];

void pre() {
    // fill(begin(prime), end(prime), true);
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1] = false;
    for (ll p = 2; p * p <= maxx; p++)
        tot_prime[p] = tot_prime[p-1];
        if(!prime[p]) continue;
        for(ll i = 2 * p; i<= maxx; i += p) {
            prime[i] = false;

int main() {
	int t; 
	while(t--) {
	    ll x,y;
	    cout<<(y - x - (tot_prime[y] - tot_prime[x + 1]))<<"\n";
	return 0;

Exactly same problem i addressed here

Your AC code

Thanks alot mate !
I got it :v:

You are welcome :grin:

in editorials solution, in the first iteration for example
“tot_primes_till[i] = tot_primes_till[i - 1]” how the value of tot_primes_till[1] will be assigned to tot_primes_till[2] as we haven’t assigned anything in that array so it should contain garbage value.

All elements are initialised to 0 if the array is declared globally. Even a Primary School kid knows this fact.

FYI: initial value of int array in C - Stack Overflow


Thanks bro

Someone kindly help!
JAVA is not able to cross the TLE error in Subtask 2.
I don’t know how to improve this.

import java.util.*;

class Codechef
final static int MAX = (int)1e7;
static boolean prime[] = new boolean[MAX+5];
static int total_primes_till[] = new int[MAX+2];

public static void sieve(){
    int n = MAX;
    Arrays.fill(prime, true);
    for(int i = 2; i <= n; i++)
        total_primes_till[i] = total_primes_till[i - 1];
        if (!prime[i])

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

public static void main (String args[])
        Scanner Sc = new Scanner(;
		int T = Sc.nextInt();
		while(T-- > 0)
		    int X = Sc.nextInt();
		    int Y = Sc.nextInt();
		    int ans = Y - X - (total_primes_till[Y] - total_primes_till[X+1]);
    catch (Exception e) 


Same problem : CHEFMGX - Editorial - #51 by ramandeep8421