You've decided to carry out a survey in the theory of prime numbers. Let us remind you that a prime number is a positive integer that has exactly two distinct positive integer divisors.

Consider positive integers a, a + 1, ..., b (a ≤ b). You want to find the minimum integer l (1 ≤ l ≤ b - a + 1) such that for any integer x (a ≤ x ≤ b - l + 1) among l integers x, x + 1, ..., x + l - 1 there are at least k prime numbers. 

Find and print the required minimum l. If no value l meets the described limitations, print -1.


-----Input-----

A single line contains three space-separated integers a, b, k (1 ≤ a, b, k ≤ 10^6; a ≤ b).


-----Output-----

In a single line print a single integer — the required minimum l. If there's no solution, print -1.


-----Examples-----
Input
2 4 2

Output
3

Input
6 13 1

Output
4

Input
1 4 3

Output
-1

Difficulty: interview

Starter code:

Solutions:
def f(n):
    m = int(n ** 0.5) + 1
    t = [1] * (n + 1)
    for i in range(3, m):
        if t[i]: t[i * i :: 2 * i] = [0] * ((n - i * i) // (2 * i) + 1)
    return [2] + [i for i in range(3, n + 1, 2) if t[i]]

a, b, k = map(int, input().split())
n = 2000001

t, p, x = [-1] * n, f(n), -1
k -= 1; b += 1

for i in range(len(p) - k):
    t[p[i]] = p[i + k] - p[i]

t.reverse()
for i in range(1, n):
    if t[i] < 0: t[i] = t[i - 1] + 1
t.reverse()

for i in range(a + 1, b):
    t[i] = max(t[i], t[i - 1])

for l in range(1, b - a + 1):
    if t[b - l] < l:
        x = l
        break
print(x)

def f(n):
    m, l = int(n ** 0.5) + 1, n - 1
    t = [1] * n
    for i in range(3, m):
        if t[i]: t[i * i :: 2 * i] = [0] * ((l - i * i) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if t[i]]

a, b, k = map(int, input().split())
k -= 1; b += 1; n = b + 100

t, p, x = [-1] * n, f(n), -1

for i in range(len(p) - k):
    t[p[i]] = p[i + k] - p[i]

t.reverse()
for i in range(1, n):
    if t[i] < 0: t[i] = t[i - 1] + 1
t.reverse()

if len(p) > k: 
    for i in range(a + 1, b):
        t[i] = max(t[i], t[i - 1])

    for l in range(1, b - a + 1):
        if t[b - l] < l:
            x = l
            break
print(x)

def f(a, b):
    t = [1] * (b + 1)
    for i in range(3, int(b ** 0.5) + 1):
        if t[i]: t[i * i :: 2 * i] = [0] * ((b - i * i) // (2 * i) + 1)
    return [i for i in range(3, b + 1, 2) if t[i] and i > a]

a, b, k = map(int, input().split())

p = f(a - 1, b)
if 3 > a and b > 1: p = [2] + p
 
if k > len(p): print(-1)
elif len(p) == k: print(max(p[k - 1] - a + 1, b - p[0] + 1))
else: print(max(p[k - 1] - a + 1, b - p[len(p) - k] + 1, max(p[i + k] - p[i] for i in range(len(p) - k))))

def main():
    def f(n):
        m = int(n ** 0.5) + 1
        t = [1] * (n + 1)
        for i in range(3, m):
            if t[i]: t[i * i :: 2 * i] = [0] * ((n - i * i) // (2 * i) + 1)
        return [2] + [i for i in range(3, n + 1, 2) if t[i]]

    a, b, k = map(int, input().split())
    n = 1100001
    
    t, p, x = [-1] * n, f(n), -1
    k -= 1; b += 1

    for i in range(len(p) - k):
        t[p[i]] = p[i + k] - p[i]
    for i in range(1,n):
        if t[-i] < 0:
            t[-i] = t[-i + 1] + 1
    for i in range(a + 1, b):
        t[i] = max(t[i], t[i - 1])
    for l in range(1, b - a + 1):
        if t[b - l] < l:
            x = l
            break
    print(x)
main()

def f(a, b):
    t = [1] * (b + 1)
    for i in range(3, int(b ** 0.5) + 1):
        if t[i]: t[i * i :: 2 * i] = [0] * ((b - i * i) // (2 * i) + 1)
    return [i for i in range(3, b + 1, 2) if t[i] and i > a]

a, b, k = map(int, input().split())

p = f(a - 1, b)
if 3 > a and b > 1: p = [2] + p
 
if k > len(p): print(-1)
elif len(p) == k: print(max(p[k - 1] - a + 1, b - p[0] + 1))
else: print(max(p[k - 1] - a + 1, b - p[len(p) - k] + 1, max(p[i + k] - p[i] for i in range(len(p) - k))))

def f(a, b):
    t = [1] * (b + 1)
    for i in range(3, int(b ** 0.5) + 1):
        if t[i]: 
            t[i * i :: 2 * i] = [0] * ((b - i * i) // (2 * i) + 1)
    return [i for i in range(3, b + 1, 2) if t[i] and i > a]

a, b, k = map(int, input().split())

p = f(a - 1, b)

if 3 > a and b > 1: 
    p = [2] + p
 
if k > len(p): print(-1)

elif len(p) == k: 
    print(max(p[k - 1] - a + 1, b - p[0] + 1))

else: 
    print(max(p[k - 1] - a + 1, b - p[len(p) - k] + 1, max(p[i + k] - p[i] for i in range(len(p) - k))))

def f(a, b):

    t = [1] * (b + 1)

    for i in range(3, int(b ** 0.5) + 1):

        if t[i]: t[i * i :: 2 * i] = [0] * ((b - i * i) // (2 * i) + 1)

    return [i for i in range(3, b + 1, 2) if t[i] and i > a]



a, b, k = list(map(int, input().split()))



p = f(a - 1, b)

if 3 > a and b > 1: p = [2] + p

 

if k > len(p): print(-1)

elif len(p) == k: print(max(p[k - 1] - a + 1, b - p[0] + 1))

else: print(max(p[k - 1] - a + 1, b - p[len(p) - k] + 1, max(p[i + k] - p[i] for i in range(len(p) - k))))



# Made By Mostafa_Khaled


p=[1]*(1000005)
p[0]=0
p[1]=0
for i in range(2,1001):
    if p[i]:
        for j in range(2*i,1000005,i):
            p[j]=0
for i in range(1,1000001):
    p[i]+=p[i-1]
a,b,k=map(int,input().split())
if p[b]-p[a-1]<k:
    print(-1);return()
i=j=a
l=0
while j<=b:
    if p[j]-p[i-1]<k:
        j+=1
    else:
        l=max(l,j-i+1)
        i+=1
l=max(j-i+1,l)
print(l)
            

I = lambda : map(int,input().split())
visited = [False for i in range (10**6+1)]
#prime = {}
a , b , k  =I()
visited[1] = True
li = []
for i in range(2,int(b**(0.5))+1) :
    #print(visited[:14])
    if visited[i] == False :
        #prime[i] = 1
        for j in range (i+i,b+1 , i) :
            visited[j] =True
for i in range (a,b+1)   :
    if visited[i] == False :
        li.append(i)
ans = 0 
maxx = 0 
#print(li)
t1 = a
#print(li)
if len(li) < k :
    print("-1");return
n = len(li)
for i in range (n-k+1) :
    ans = li[i+k-1] -t1 + 1
    #print(ans)
    maxx = max(maxx,ans)
    t1 = li[i] + 1
ww = b - li[-k] + 1
#print(ww)
maxx = max(ww,maxx)
print(maxx)

import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

a,b,k = mints()

p = [True]*(b+1)
for i in range(2, b+1):
	if p[i]:
		for j in range(i*i, b+1, i):
			p[j] = False

p[1] = False
#d = []
#for i in range(a, b+1)
#	if p[i]:
#		d.append(i)
c = 0
i = a
q = [0]*(b+1)
ql = 1
qr = 1
q[0] = a-1
while c < k and i <= b:
	if p[i]:
		c += 1
		q[qr] = i
		qr += 1
	i += 1
if c != k:
	print(-1)
	return
#print(q[qr-1],a)
r = q[qr-1]-a
while i <= b:
	#print(r, q[qr-1],q[ql-1]+1)
	r = max(r, q[qr-1]-(q[ql-1]+1))
	ql += 1
	c -= 1
	while i <= b:
		if p[i]:
			q[qr] = i
			qr += 1
			c += 1
			i += 1
			break
		i += 1
if c == k:
	#print(r, b, q[ql-1]+1)
	r = max(r, b-q[ql-1]-1)
else:
	#print(r, b, q[ql-1])
	r = max(r, b-q[ql-1])
print(r+1)

from math import floor, sqrt


def siv(limit, primes):
    mark = [False] * (limit + 1)
    for i in range(2, limit + 1):
        if not mark[i]:
            primes.append(i)
            for j in range(i, limit + 1, i):
                mark[j] = True


def pir(low, high, prims):
    limit = floor(sqrt(high)) + 1
    primes = list()
    siv(limit, primes)
    n = high - low + 1
    mark = [False] * (n + 1)
    for i in range(len(primes)):
        loLim = floor(low / primes[i]) * primes[i]
        if loLim < low:
            loLim += primes[i]
        if loLim == primes[i]:
            loLim += primes[i]
        for j in range(loLim, high + 1, primes[i]):
            mark[j - low] = True
    pc = 0
    for i in range(low, high + 1):
        if not mark[i - low]:
            prims.append(i)
            pc += 1
    return pc


a, b, k = [int(i) for i in input().split()]

prims = []
pc = pir(a, b, prims)
if pc!= 0 and prims[0] == 1:
    prims.remove(1)
    pc-=1

if pc < k:
    print(-1)
    return

mx = max(prims[k - 1] - a + 1, b - prims[len(prims) - k] + 1)

for i in range(len(prims) - k):
    mx = max(prims[i + k] - prims[i], mx)

print(mx)