A prime gap is the difference between two consecutive primes. More specifically, if p and q are primes with p <q and p+1, p+2, ..., _q_−1 are not primes, the primes p and q define a gap of n = q_−_p. The gap is said to be started by p, and to have length n.
It is known that arbitrarily large prime gaps exist. That is, given n there exists a prime gap of length n or larger. However, a prime gap of length exactly n may not exist (but a larger one will).
Given a positive integer
n, output the first prime that starts a gap of length
n or larger.
As an example, for input
4 the output should be
7, because 7 and 11 are the first consecutive primes that differ by at least 4 (the previous gaps are 1, from 2 to 3; 2, from 3 to 5; and 2, from 5 to 7). For input
3 the answer should also be
7 (there are no gaps of length 3).
The algorithm should theoretically work for arbitrarily high
n. In practice, it is acceptable if the program is limited by time, memory or data-type size.
Input and output can be taken by any reasonable means.
Shortest code in bytes wins.
Input -> Output 1 2 2 3 3 7 4 7 6 23 10 113 16 523 17 523 18 523 30 1327 50 19609 100 370261 200 20831323