chickenstrips

You're correct. The correspondence just seems to be due to some bound on the prime gap for arithmetic progressions (or perhaps something even more trivial that I'm missing). A cursory search suggests it might be a consequence of Ingham's bound. In any case, it doesn't yield much of interest.

For fixed n, a block (x,y) contains the numbers n/2y^2-n/2y + yz + x for all 0 <= z < n.

It also doesn't reduce the time to O(1). Each of the ranges is of size O(2^(N/2)) for an N bit prime, so it's really not useful at all.

No, this won't help with finding primes. As they noted, the pattern for ranges of size k only holds for k lines. So to find a prime of length N (on the order of 2^N), we need to have k=O(2^(N/2)). However, this yields a guarantee that a prime lies in a range of size O(2^(N/2)), which is not particularly useful. We get exponentially better probabilistic results from the prime number theorem.