For how many numbers $1\le k\le n$ does there exist $a$, $b\in\Bbb Z$, so that $k=a^2+b^2$? Give an approximation, focus more on the lower bound.
Let the number be $f(n)$. First, I know the following.
Let $k=p_1p_2\cdots p_tM^2$, where $p_i$ are prime($1\le i\le t$), and $M\in\Bbb N$.
$\exists~a$, $b\in\Bbb Z$, so that $n=a^2+b^2$ $\iff$ $\forall~1\le i\le t$, $p_i\not\equiv3\pmod4$.
So I tried to do \[f(n)\ge n-\sum_{\text{prime }p\le n}\sum_{i}\frac{n(-1)^{i+1}}{p^i}=n-\sum_{\text{prime }p\le n}\frac1{1+p}.\] But it doesn't work. However, the $f(n)$ seems quite large.
Here is a heuristic justifying why $f(m)\sim\frac{m}{\sqrt{\ln m}}$:
We know that $n$ is representable iff it is divisible by $r^{2k}$ but not $r^{2k+1}$ for all primes of the form $r\equiv 3\pmod 4$. Now for a given $r$, the proportion of numbers not divisible by $r$ is $1-\frac{1}{r}$, but we then want to include those divisible by $r^2$ so we multiply by $\sim1+\frac{1}{r^2}$, but then we don't want to include those divisible by $r^3$ so we multiply by $\sim1+\frac{1}{r^3}$, and so on and so forth.
Now consider all such $r$. This gives us
$$f(m)\sim m\prod_{r\leq \sqrt m}\left(1-\frac{1}{r}\right)\prod_{r^2\leq \sqrt m}\left(1+\frac{1}{r^2}\right)\prod_{r^3\leq \sqrt m}\left(1-\frac{1}{r^3}\right)\cdots$$
By binomial expansion, the terms past $1-\frac{1}{r}$ converge to a finite number, so we ignore them. Hence,
$$f(m)\sim m\prod_{r\leq \sqrt m}1-\frac{1}{r}$$
By Dirichlet's Theorem, about half of all primes are $3\pmod 4$. Hence,
\begin{align*} \ln\prod_{r\leq\sqrt m}1-\frac{1}{r}&=\sum_{r\leq\sqrt m}\ln\left(1-\frac{1}{r}\right)\\ &\approx\frac{1}{2}\sum_{p\leq\sqrt m}\ln\left(1-\frac{1}{p}\right)\\ &=\frac{1}{2}\ln\left(\prod_{p\leq\sqrt m}1-\frac{1}{p}\right)\\ &\approx-\frac{1}{2}\ln\sum^m_{k=1}\frac{1}{k}\\ &\approx-\frac{1}{2}\ln\ln m=\ln\left(\sqrt{\ln m}\right)^{-1}\\ \end{align*}
Or in other words,
$$f(m)\sim \frac{m}{\sqrt{\ln m}}$$
Proving that the proportionality constant is equal to $\lambda=\left(\frac{1}{2}\prod\frac{1}{1-r^{-2}}\right)^{\frac12}$ is rather tricky (and will need analytic number theory knowledge). The proof is a bit too complicated for here, but you can read "Topics in Number Theory Vol. II" by William J. Leveque for more details.
You may also be interested in this article, which uses zeta functions to quickly find $\lambda$, or higher order approximations for $f(m)$.