An algorithm and computation to verify Legendre's Conjecture up to 3.33⋅10^13

We state a general purpose algorithm for quickly finding primes in evenly divided sub-intervals. Legendre's conjecture claims that for every positive integer  n , there exists a prime between  n 2  and  ( n +1) 2 . Oppermann's conjecture subsumes Legendre's conjecture by claiming there are primes between  n 2  and  n ( n +1)  and also between  n ( n +1)  and  ( n +1) 2 . Using Cramér's conjecture as the basis for a heuristic run-time analysis, we show that our algorithm can verify Oppermann's conjecture, and hence also Legendre's conjecture, for all  n ≤ N  in time  O ( N log N loglog N )  and space  O (1/loglog N ) . We implemented a parallel version of our algorithm and improved the empirical verification of Oppermann's conjecture from the previous  N =2⋅10 9  up to  N =3.33⋅10 13 , so we were finding  27  digit primes. The computation ran for about half a year on four Intel Xeon Phi  7210  processors using a total of  256  cores.