# nth_prime

Marco Bodrato bodrato at mail.dm.unipi.it
Tue May 21 22:26:12 UTC 2019

Ciao,

Il Mar, 21 Maggio 2019 8:49 pm, Niels Möller ha scritto:
> Seth Troisi <braintwo at gmail.com> writes:
>
>> 3. Use Legendre's Formula (github
>> <https://github.com/sethtroisi/libgmp/pull/9>)

Me too, I'm interested by this implementation.

> It seems clear that an efficient nth prime can be implemented on top of
> an efficient \pi(k) = (number of primes <= k): Given n, first find some

And this seems exactly the idea implemented in that code. But I'm more
interested about the implementation of \pi(k). A single loop on the sieve
is used to build a list, and then the loops are on the list; why not using
directly the sieve to loop on primes?

I'll read more carefully on that code.

Ĝis,
m

--
http://bodrato.it/papers/