оценка "сколько нужно" должна гарантировать абсолютное отклонение от истинного номера меньше 2
Зачем?

.
Если мало, просеиваем числа, меньшие

, находим

,

,

.
Если мало, просеиваем числа, меньшие

, находим

,

,

,

,

.
Если мало, просеиваем числа, меньшие

, находим

,

,

,

,

,

.
Если мало, просеиваем числа, меньшие

, ...
Никаких априорных оценок для этого алгоритма не требуется. Другое дело, что он, разумеется, очень далёк от оптимальности. Например, на моём компьютере Wolfram Mathematica 5.1 находит

за

секунды и

за

секунды. Ясно, что в этом случае сплошным просеиванием она не занимается. В описании функции
![$\mathbf{Pime[n]}$ $\mathbf{Pime[n]}$](https://dxdy-04.korotkov.co.uk/f/b/b/f/bbf8f803b2c5d056d09745bd5a58321e82.png)
сказано:
Цитата:
Prime and PrimePi use sparse caching and sieving. For large

, the Lagarias‐Miller‐Odlyzko algorithm for PrimePi is used, based on asymptotic estimates of the density of primes, and is inverted to give Prime.