spoj NthPRIME

Can anyone suggest some approach to solve nth prime, link is here:

http://www.spoj.com/problems/NTHPRIME/

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

@likecs can you explain in easy words how to count the number of primes?

//