I think it's a simple task.
Let's make problem simplely. pi(n)<=A*rub(n) <=>pi(n)<=p/q*rub(n) <=>pi(n)*q<=p*rub(n) So we don't need to use double
We know that Max n <= 2e6 So we can prefix n 1 to 2e6 How to get pi&rub? We can use DP.
for(i=2;i*i<=n;i++)//O(n) get prime
if(isp[i])
for(j=i*i;j<=n;j+=i)
isp[j]=false;
pi[0]=pi[1]=0;//both 1 and 0 isn't prime
for(i=2;i<=n;i++)
if(isp[i])pi[i]=pi[i-1]+1;//because i is a prime
else pi[i]=pi[i-1];
for(i=1;i<=n;i++)
if(is_palind(i))rub[i]=rub[i-1]+1;
else rub[i]=rub[i-1];
//How to write _is_palind(i)_?
bool is_palind(int x){
int k=0,tmp=x;
while(x){k=k*10+x%10;x/=10;}//reserve x
if(k==x)return true;
else return false;
}
So the code is O(n)
Thanks.