$\pi(n) = \text{ number of prime number smaller than or equal to n}$ . $rub(n) = \text{ number of palindromic number smaller than or equal to n}$ . For a given $p$ and $q$ find maximum such $n$ so that, $\pi(n)\le \frac{p}{q}\times rub(n)$ Inside Math: $\pi(n) \approx \frac{n}{ln(n)}$ [Prime number approximation] $rub(n) \approx 2\sqrt{n}$ maximum value of $\frac{p}{q} = 42$ Hence , \begin{align} \pi(n) &\le \frac{p}{q}\times rub(n) \newline \Longrightarrow \frac{n}{ln(n)} &\le 42 \times 2\sqrt{n} \newline \Longrightarrow \frac{\sqrt{n}}{ln(n)} &\le 84 \newline \Longrightarrow n_{max} &\approx \boxed{1415344} \newline \end{align}

In this problem we will run a segmented sieve for [l,r]. In sieve we will maintain “number of divisor of $n$ which is smaller or equal than $\sqrt{n}$". For each, $i\in [1,\sqrt{r}]$ we will increase number of divisor of each multiple of $i$ in range $[max(l,i^2),r]$. After the sieve we will multiply $2$ with each number of divisor, because if $i$ is a divisor of $n$ such that $i\le \sqrt{n}$ , we will have another divisor $\frac{n}{i} \ge \sqrt{n}$.

Find sum of sum-of-divisor from 1 to n