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