Can anyone suggest some approach to solve nth prime, link is here:
You can perform binary search on the answer.
Now, for a particular number, you would need to find the number of primes numbers below it. This is a standard problem, the tutorial of which can be found in problem F of educational round 12 on codeforces. Link.
The pseudo code is as :
<pre>
low = 0, high = 1e18, ans = -1
while(low <= high)
{
mid = (low+high)/2
if (count_primes(mid) < n) {
low = mid + 1
}
else {
ans = mid
high = mid - 1
}
}
print(ans)
</pre>
The complexity of the above solution is O(K * \log{n}), where O(K) is the complexity of finding number of primes below given number. According to editorial, O(K) ~ O({n}^{2/3} {\log{n}}^{1/3})
1 Like