Given a large integer $z \in \mathbb{Z}$, what algorithms are available to compute a prime number larger than $z$ and close to $z$, efficiently, but not necessarily the closest?
e.g. Given the number $400$, any of $\{401, 409, 419, 421, 431, 433, ...\}$, would be acceptable.
Noting that for large integers, the solutions aren't so trivial to compute.
Mathematica gives the next prime blazingly fast:
$10^{617} + 2607$
in $0.858659$ seconds.
That oughta suffice....
(You can enter this code for free on WolframAlpha.com)
Although Mathematica doesn't state the upper limitation of their algorithm, I think that is moot, in practice. (The OP asked about neighboring primes to 400 and wasn't concerned that the algorithm get the closest prime.)
Without you specifying the criteria for membership in your subset, we can never help you.