Link to question:
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll a[10000003];
vector<long long int> v;
void sieve(ll start,ll end)
{
int i=0,j=0,sum=1;
a[1]=0;
if(start==1)
start+=1;
for(i=(start);i<=end;i++)
{
if(a[i]!=i)
continue;
for(j=(2*i);j<=end;j+=i)
{
a[j]=0;
}
a[i]=1;
}
}
int main()
{
ll n=10000000,i=0,j=0,k=0,t=0,l=0,r=0,count=0;
//ios_base::sync_with_stdio(0);
for(i=1;i<=n;i++)
a[i]=i;
sieve(2,n);
for(i=2;i<=n;i++)
a[i]=a[i-1]+a[i]; //prefix_sum array
//k=v.size();
//for(i=1;i<=10;i++)
// cout<<a[i]<<" ";
cin>>t;
while(t--)
{
scanf("%lld %lld",&l,&r);
l=(ll)sqrt(l);
r=(ll)sqrt(r);
printf("%lld\n",a[r]-a[l]);
}
return 0;
}
This is my solution…I am applying sieve to generate all prime numbers upto 10^7 and then maintaining a prefix array which stores the number of primes calculated till now(as the constraints are too large)…The solution is running well on the first 2 test cases,but givin WA on the 3rd,seems there is some minor error…can anyone please help me,where i am getting wrong and how to modify it?