 # CHEFMGX - Editorial

ig the solution might have been updated you can see RE here
https://www.codechef.com/viewsolution/52761056

Ohk . Thanks dude

Can anyone help!!

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;
while(b){
if(b%2!=0){
res = (resa)%MOD;
}
a = (a
a)%MOD;
b/=2;
}
return res;
}

bool IsPrime(int a){
if(a==1) return false;
bool ans = true;
for(int i=2;i<=sqrt((double)a);i++){
if(a%i==0){
ans = false;
break;
}
}
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;
while(i<=j){
swap(s[i],s[j]);
i++;j–;
}
}
const int MAX = 1e7+1;
vector sieve(MAX, true);
vector primeInRange(MAX,0);

void sieveOfEratosthenes(){
sieve = sieve = false;
for(int i=2;ii<MAX;i++){
if(sieve[i]){
for(int j = i
i; j<=MAX ; j+=i){
sieve[j] = false;
}
}
}
primeInRange = 1;
for(int i=3;i<MAX;i++){
if(sieve[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(){
sieveOfEratosthenes();
int t=1;
cin >> t;
while(t–){
solve();
}
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 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 https://www.codechef.com/viewsolution/52856555

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

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 = prime = false;

for (ll p = 2; p * p <= maxx; p++)
{
tot_prime[p] = tot_prime[p-1];

if(!prime[p]) continue;

tot_prime[p]++;

for(ll i = 2 * p; i<= maxx; i += p) {
prime[i] = false;
}
}
}

int main() {

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

int t;
cin>>t;

pre();

while(t--) {
ll x,y;
cin>>x>>y;
cout<<(y - x - (tot_prime[y] - tot_prime[x + 1]))<<"\n";
}

return 0;
}
``````

Exactly same problem i addressed here https://discuss.codechef.com/t/chefmgx-editorial/95496/51?u=ramandeep8421

Thanks alot mate !
I got it You are welcome 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 will be assigned to tot_primes_till 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.

2 Likes

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])
continue;

total_primes_till[i]++;

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

public static void main (String args[])
{
try
{
Scanner Sc = new Scanner(System.in);
int T = Sc.nextInt();
sieve();
while(T-- > 0)
{
int X = Sc.nextInt();
int Y = Sc.nextInt();
int ans = Y - X - (total_primes_till[Y] - total_primes_till[X+1]);
System.out.println(ans);
}
}
catch (Exception e)
{
return;
}
}
``````

}

Same problem : CHEFMGX - Editorial - #51 by ramandeep8421

why my code is giving error if i am using n=10000001 instead of n=1e7+1(by this code has been submitted successfully).

Here’s my code:

#include
#include <bits/stdc++.h>

#define ll long long
#define loopi(s,n) for(int i=s;i<n;i++)
#define loopd(s,n) for(int i=n-1;i>=s;i–)
#define pi pair<int,int>
#define vi vector

#define n 10000001 // giving error on using this but submitted successfully if n=1e7+1 is taken.

using namespace std;

vector prime(n,1);
vector arr(n,1);

void sieve()
{

``````for(int i=2;i<=n;i++)
{
if(prime[i])
{
for(int j=2*i;j<=n;j+=i)
prime[j]=0;
}
}
int curr=0;
arr=arr=0;
for(int i=2;i<=n;i++)
{
curr+=prime[i];
arr[i]=curr;
}
``````

}

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

``````int t;
cin>>t;
sieve();
while(t--)
{
int x,y;
cin>>x>>y;

cout<<(y-x)-(arr[y]-arr[x+1])<<endl;

}

return 0;
``````

}

Tell me you never used Fast IO.

He has written 10000001 viz., 1e7 + 1.

1 Like