Here is a suggestion for a problem related to the one you are asking. I will give the two dimensional version; perhaps Joseph O'Rourke will be intrigued enough to illustrate this or a 3 or higher dimensional version for us.

I will suggest a coloring/labeling for an integer grid, with x and y coordinates being all integers greater than m respectively n. I recommend m=1 and n=1 ranging up to 40, but you can choose differently depending on your graph paper. Also, you can decide whether to take advantage of symmetry or not and restrict yourself (or not) to the region x <= y.

Each coordinate (x,y) will be assigned the integer xy+1, but do not label every such coordinate. Instead, use whatever color scheme to sieve out nontrivial multiples of 2 (meaning x and y are both odd, and xy>1), interesting multiples of 3 (those pairs where xy = 2 mod 3 and xy >2), big multiples of 5, and so on, not forgetting to mark the primes encountered. That is, label a coordinate (x,y) with xy + 1 only if that quantity is prime.

You will end up with a colored grid, with the colors having a pleasing pattern (I think) and a look up chart for small m and n of primes greater than mn, where you look at or above and to the right (if you use my orientation) of the coordinate (m,n) for such primes, and try to find the smallest one of the nearest such primes. From generating such a chart for various m,n, you may get a sense of how close heuristically your desired prime is. I predict the value of the smallest such prime p(mn)= 1 + (m+i)(n+j) for nonnegative i and j satisfies p(mn) < (n+m)*m*n for positive integers m,n.

Gerhard "Ask Me About Prime Guesses" Paseman, 2011.10.04

2more comments