The prime_pi function sometimes computes a wrong result. In particular, I found the following errors:

• prime_pi(14783545363230719)
  returns 408351706116074, it should be 408351706116078
• prime_pi(5685979153167559)
  returns 161319877461134, it should be 161319877461136
• prime_pi(642763101936913)
  returns 19439675999018, it should be 19439675999019

The correct countings are computed using Kim Walisch's primecount library, with different algorithms: Deleglise-Rivat, Lagarias-Miller-Odlyzko and Lehmer's formula. All of them return the same result.

Note that while the arguments to prime_pi in the first two examples exceed the value 2!^50, causing the appearance of a warning ("computation of prime_pi for x >= 2!^50 has not been as thoroughly tested as for smaller values"), the argument of the last example is within the range of inputs considered to be safe.

Actually, instead of fixing the current code, it could be easier to rewrite the prime_pi function and let it use the primecount library. This would have the additional advantage of being much faster than the current code. The table below compares the execution times (in seconds) of primecount with Deleglise-Rivat, primecount with Lagarias-Miller-Odlyzko and SageMath prime_pi function.

All results have been obtained with an Intel i5-2500K. For primecount, a single thread has been used.

| ||| argument |
|-|||:----------:|
| algorithm | 642763101936913 | 5685979153167559 | 14783545363230719 |
| primecount | 2.99| 11.168| 20.052|
| primecount --lmo | 5.287| 21.883| 41.286|
| prime_pi | 331| 2489| 6083|

Here we take the route of replacing Cython code in sage.functions.prime_pi
with calls to functions in sage.interface.primecount

Will be fixed by #32894

Depends on #25009

CC: @slel

Component: number theory

Keywords: primes prime_pi primecount

Branch/Commit: u/dimpase/functions/prime_pi-fix @ 4f77073

Issue created by migration from https://trac.sagemath.org/ticket/24960