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.

Making sure I am parsing that correctly:

Is that

((n/2) * y^2) - ((n/2) * y) + (y * z) + x ? (For z ranging from 0 to n)

If so, alright, that makes more sense to me, thanks.

So, n * (y * (y-1)/2) + x + y * z ?

Edit: does HN have an escape character to deal with the asterisks?

Having whitespace after the asterisk or indenting the line by two or more spaces seem to be the only possibilities according to the "Formatting Options"[1]

[1]https://news.ycombinator.com/formatdoc

(n/2)y^2-(n/2)y + yz + x

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.