In this problem, we have to find the nearest prime number smaller than N and greater than N. (3 <= N <= 2^32).

I have used Miller Rabin but it’s showing TLE.

Similar problem:

http://www.spoj.pl/problems/PAGAIN/

You need Sieve of Eratosthenes algorhitm. you can this view here: