# Prime equivalency in hackerrank

``````#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?

As much i understood,it need to calculate numbers having exactly 3 factors,which u r not doing!
See numbers having exactly 3 factor are square numbers whose square root is also prime.eg 4 has 3factors but 36 has not.So precompute such squares(u precomputed sieve,need looping from 1 to sqrt(10**14) to check if prime or not )and ans in O(1).

The same thing i can say that for a given query say l,r i need to find the number of prime numbers lying between sqrt(l) and sqrt®.This is what i have done…what’s wrong in that…that is why i already computed such prime numbers(upto 10**7).

//