And there is one more thing we should notice is that every single query about \text{WA} or \text{RTE} or even \text{TLE} posted have an out-of-bounds access - because of the Setter’s solution.
@ajit123q can you please update the Setter’s solution? It has out-of-bound access in the Sieve function. If unsure, replace the Setter’s solution with the following.
Setter's Code, edited
#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++) // a change is here
{
for(int j=2;i*j<n;j++) // another change
{
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++) // another change
{
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";
}
}
you used the vector of size 1e8, and we can not complete 10^8 iteration in 1 second time and as @ramandeep8421 said, no need to compute primes in between every time, pre-compute it beforehand
My Python code passes one set of tests, but runs into TLE for the other. Can anyone tell me what is causing this please? - can’t seem to figure it out!
