The Next Prime — Solution & Editorial

Back to the Problem

Test candidates N+1, N+2, ... for primality with √-trial division or Miller–Rabin. Prime gaps near 10¹² are tiny (< 400), so few candidates are tested.

Complexity: O(gap · √N) with trial division — fast in practice