Wikipedia has an excellent article on prime gaps. It presents a table of the first 75 maximal gaps.
It is straight forward to identify each of these gaps using a brute forth method that iterates through odd numbers (or some other skipping mechanism such as $i=5$; check $i,i+2$ if prime; and $i=i+6$).
I am interested if there is an algorithm that can be used that does not employ the brute force method? For the purposes of MSE, I am more interested in the mathematical explanation (rather than a code sample)
It occurs to me, for example, that the following algorithm could be used to find the first maximal gaps that occur before some prime $p^2$
(1) Start with $\{1,5\}$ which represents the gaps between numbers that are relatively prime to $6$. At this point, the largest gap is $4$ which is found at $1+6 = 7$ and the largest gap is $4$.
(2) Multiply $5$ to $\{1,5\}$ to get $\{5,25\}$ and subtract these numbers from the first $5$ instances $\{(1,5),\, (7,11),\, (13,17),\, (19,23), (25,29)\}$ to get $\{1,7,11,13,17,19,23,29\}$ At this point, the largest gap between numbers relatively prime to $30$ is $6$ and the first one that doesn't include primes is found at $23$.
(3) Multiply $7$ to $\{1,7,11,13,17,19,23,29\}$ to get $\{7, 49, 77, 91, 119, 133, 161, 203\}$ and subtract these numbers from the first $7$ instances of
$\{(1,7,11,13,17,19,23,29), (31,37,41,43,47,49,53,59), (61,67,71,73,77,79,83,89), (91,97,101,103,107,109,113,119), (121,127,131,133,137,139,143,149), (151,157,161,163,167,169,173,179), (181,187,191,193,197,199,203,209) \}$
to get:
$\{1,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,121,127,131,137,139,143,149,151,157,163,167,169,173,179,181,187,191,193,197,199,209\}$
At this point, the largest gap is $10$ at $199$. As we repeat these steps, at $p=11$ we find a gap of $14$ at $113$.
After each step using prime $p$, the largest gap is the highest sum of two consecutive gaps in the previous step.
We can repeat this process with as many primes as we like.
In step #1, the highest sum of two consecutive gaps is $6$. In step #2, the highest sum of two consecutive gaps is $10$ and in step #3, the highest sum of two consecutive gaps is $14$. We can likewise use each step to predict the largest gap found in the next step.
Ignoring the brute force method, is there a better algorithm that can be used for determining prime gaps?