https://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number https://en.wikipedia.org/wiki/Prime_number_theorem#Approxima... So w

https://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number https://en.wikipedia.org/wiki/Prime_number_theorem#Approxima... So with the kth prime ~= k log k, the ratio of primes is 1 / log k. Yes that drops to zero, but very slowly. You can use the upper bound of the kth prime to build a sufficiently large sieve, which can be done O(n).