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.
ig the solution might have been updated you can see RE here
https://www.codechef.com/viewsolution/52761056
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;
while(b){
if(b%2!=0){
res = (resa)%MOD;
}
a = (aa)%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[0] = sieve[1] = false;
for(int i=2;ii<MAX;i++){
if(sieve[i]){
for(int j = ii; j<=MAX ; j+=i){
sieve[j] = false;
}
}
}
primeInRange[2] = 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: CodeChef: Practical coding for everyone. 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
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;
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
Your AC code https://www.codechef.com/viewsolution/52896630
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[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.
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;
}
}
}