How does $\sum p(k)$ grow asymptotically where $p(k)$ is the smallest prime factor of $k$? Define $p(k)$ to be the smallest prime $p$ dividing $k$. Define $A(n)=\sum_{k=2}^n p(k)$. How does $A(n)$ grow asymptotically? I am wondering how exactly the naive algorithm for finding all primes less than and equal to $n$ by testing for divisibiity of all numbers less than $k$ for each $k<n$ actually performs. It's very easy to see it is $O(n^2)$ but there must be a better bound.
 A: Let $q$ denote a prime, and let
$$
s(n) = \sum_{q\le n} q = \frac{n^2}{2\log n} + O\left(\frac{n^2}{\log^2 n}\right)
$$
as discussed on MathOverflow. Clearly
$
s(n) = \sum_{q\le n} p(q) \le A(n)
$.
Define the sets
$$
S_q(n) = \{1<k\le n, p(k)=q \}
$$
If $\sqrt{n}<q\le n$ then $\left\vert S_q(n)\right\vert = 1$, and for every $q$
$$
\left\vert S_q(n)\right\vert \le \left\lfloor\frac{n}{q}\right\rfloor
$$
since this counts all multiples of $q$ in the range, which must be a superset of $S_q$. Hence
$$
\begin{align}
A(n) & = \sum_{q\le n} q\left\vert S_q(n)\right\vert \\
& \le \sum_{q\le \sqrt{n}} q\left\lfloor\frac{n}{q}\right\rfloor + \sum_{\sqrt{n}<q\le n} q \\
& \le \sum_{q\le \sqrt{n}} q \left(\frac{n}{q}\right) + \sum_{q\le n} q \\
& = \sum_{q\le \sqrt{n}} n + s(n) \\
& = n\pi\left(\sqrt{n}\right) + s(n) \\
& = s(n) + O\left(\frac{n^{3/2}}{\log n}\right)
\end{align}
$$
where $\pi(\cdot)$ is the prime counting function.
Thus $A(n)$ has asymptotic behavior similar to $s(n)$,
$$
A(n) = \frac{n^2}{2\log n} + O\left(\frac{n^2}{\log^2 n}\right)
$$
