TITLE: Efficiently computing $\sum_{\sqrt{N} \lt p \in primes \leq N} \lfloor \frac{N}{p} \rfloor$
QUESTION [0 upvotes]: I'm interested in computing $f(N) = \sum_{\sqrt{N} \lt p \in primes \leq N} \lfloor \frac{N}{p} \rfloor$
$N$ is large enough that primes up to $\sqrt{N}$ are available, but not much beyond and certainly not to $N$.
There's some flexibility about the range, in that a $g(N)$ summing over $1 \lt p \in primes \leq N$ would be just as useful and give $f(N) = g(N)-g(\sqrt{N})$.
The most/only obvious improvement I can think of - compared with the completely infeasible prime search up to $N$ - is using the prime counting function $\pi(n)$: there are $\pi(N)-\pi(\frac{N}{2})$ primes contributing 1 to the sum, $\pi(\frac{N}{2})-\pi(\frac{N}{3})$ primes contributing 2 to the sum and so on.  However while there seem to be practical implementations for computing $\pi(N)$ using only primes to $\sqrt{N}$ (e.g sympy's primepi), in practice the computational complexity means $\pi({N})$ still seems to be out of practical reach.
Is there any trick which will help compute this sum?

REPLY [0 votes]: As the comment thread under my question reveals, the fundamental issue here was that I just didn't understand how fast prime counting can be.  Kudos to libprimecount which can do astonishing (to me) numbers like $10^{18}$ in a matter of seconds.
Using that, I was able to solve my problem easily.
Using the prime counting function $\pi(n)$, the sum in the question can be evaluated by
$\sum_{k=1}^{\sqrt{N}-1} k.(\pi( \lfloor {\frac{N}{k}} \rfloor ) - \pi( \lfloor \frac{N}{k+1} \rfloor ))$
or
$ - (\sqrt{N}-1).\pi( \lfloor \sqrt{N} \rfloor ) + \sum_{k=1}^{\sqrt{N}-1} \pi({ \lfloor \frac{N}{k}} \rfloor ) $
And as a check, some python code, just using sympy's prime tools, nothing fancy.  bfS is the literal implementation of the question, and S and T implement the two forms above.
from sympy.ntheory.generate import primerange
from sympy.ntheory import primepi

def check(N):

    sqrtN=int(N**0.5)
    assert sqrtN**2<=N
    assert (sqrtN+1)**2>N

    # Bruteforce it
    bfS=sum(N//p for p in primerange(sqrtN+1,N+1))

    # Use primepi
    kpi={k:primepi(N//k) for k in range(1,sqrtN+1)}
    S=sum(k*(kpi[k]-kpi[k+1]) for k in range(1,sqrtN))
    assert S==bfS

    T=sum(kpi[k] for k in range(1,sqrtN)) - (sqrtN-1)*primepi(sqrtN)
    assert T==bfS

for e in range(1,7):
    check(10**e)
{"set_name": "stack_exchange", "score": 0, "question_id": 3746591}