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