Re: `primepi()` is significantly slower that sage's `primepi()`

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Mon, Jan 22, 2024 at 12:51:30PM +0200, Georgi Guninski wrote:
> `primepi()` is significantly slower that sage's `primepi()`
> 
> ? primepi(10^11)
> %59 = 4118054813
> ? ##
>   ***   last result computed in 5,285 ms.
> 
> in sage:
> 
> sage: time prime_pi(10**11)
> CPU times: user 31.3 ms, sys: 0 ns, total: 31.3 ms
> Wall time: 48.3 ms
> 4118054813

This is true. Sagemath use primecount
<https://github.com/kimwalisch/primecount/releases>
which use fast algorithms while PARI use a standard sieve.
In your example, I understand it is using Gourdon's algorithm.
(Interestingly, Xavier Gourdon wrote the original polroots code in PARI).

Cheers,
Bill.