How to get upper bound on size of array for sieve of Eratosthenes?

In sieve of eratosthenes algorithm to find the prime numbers in a given range, we declare a boolean array of size n for marking the prime numbers. How can we get an upper bound on the value of n for finding the kth prime number?

Ok as far as I understand, you want to know the value of n, such that there are p primes less than n.
This falls under the topic called Prime-counting function denoted by π.
π(n) = Number of primes less than or equal to n.
π(n) can be approximated as: n / ln(n).
So you can approximate p’th prime as: p * ln(p).
An upper is provied as p * ln(p * ln(p)).

1 Like