What this boils down to is a highly optimized Sieve of Eratosthenes. To me, this optimization feels "complete," characterized more by the optimization itself than by the original Sieve.
Beginning with five, primes are one-off multiples of six. Let's arrange these candidate primes like this:
| 6n−1 | n | 6n+1 |
|---|---|---|
| 5 | 1 | 7 |
| 11 | 2 | 13 |
| 17 | 3 | 19 |
| 23 | 4 | 25 |
| 29 | 5 | 31 |
| 35 | 6 | 37 |
| 41 | 7 | 43 |
| 47 | 8 | 49 |
| 53 | 9 | 55 |
| 59 | 10 | 61 |
| 65 | 11 | 67 |
| 71 | 12 | 73 |
| 77 | 13 | 79 |
| 83 | 14 | 85 |
| 89 | 15 | 91 |
| 95 | 16 | 97 |
| … | … | … |
At this point all candidates are presumed prime. Thus, 5 is the first prime obtained from this method. Whether the prime p is found on the 6n−1 column or the 6n+1 column, p2 is always on the 6n+1 column so we'll go there first to eliminate composites. (It's not necessary to search for composites less than p2 because those will have been stricken already during the iteration from a smaller prime.)
If prime p, like 5, is found on the 6n−1 column, p2 is found on the 6n+1 column on the (n(p−1))th line. This refers to the n of p. In the cases of 5 and 7, 1; in the cases of 11 and 13, 2 …
If prime p, like 7 (the second prime found), is found on the 6n+1 column, p2 is found on the 6n+1 column on the (n(p+1))th line.
In either case, if we call this number, the n of p2 , q, the other composites of p on the 6n+1 column will be found at q+p, q+2p, q+3p …
If prime p, like 5, is found on the 6n−1 column, the first composite of p greater than p2 on the 6n−1 column is found on the (q+2n)th line.
If prime p, like 7, is found on the 6n+1 column, the first composite of p greater than p2 on the 6n−1 column is found on the (q+4n+1)th line.
In either case, if we call this number, the n of the first composite of p greater than p2 on the 6n−1 column, r, the other composites of p on the 6n−1 column will be found at r+p, r+2p, r+3p …
When I first worked this out some years ago, I shopped it to a few refereed journals, to no avail. Although I certainly didn't plagiarize it, I have no way of ascertaining that someone, maybe someone famous, didn't see it centuries ago. And conceivably, to a sufficiently skillful mathematician, the whole thing is obvious, or "trivial." I never got anything like that from the rejections though …
Correspondence to: primes[at]xbracket.com