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

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Number theory

Sorting

Amortized analysis


Solutions:
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(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)


I = lambda : map(int, input().split())
visited = [False for i in range(10 ** 6 + 1)]
(a, b, k) = I()
visited[1] = True
li = []
for i in range(2, int(b ** 0.5) + 1):
	if visited[i] == False:
		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
t1 = a
if len(li) < k:
	print('-1')
	return
n = len(li)
for i in range(n - k + 1):
	ans = li[i + k - 1] - t1 + 1
	maxx = max(maxx, ans)
	t1 = li[i] + 1
ww = b - li[-k] + 1
maxx = max(ww, maxx)
print(maxx)


def isprime(a):
	if a < 2:
		return False
	if a == 2:
		return True
	for h in range(2, int(a ** 0.5) + 1):
		if a % h == 0:
			return False
	return True
(a, b, k) = map(int, input().split())
arr = []
for g in range(a, b + 1):
	if isprime(g):
		arr += [g]
check = a
ptr1 = -1
ptr2 = 0
count = 0
n = len(arr)
maxm = 0
if n < k:
	print(-1)
else:
	while ptr2 < n:
		count += 1
		if count >= k:
			if count == k:
				maxm = max(maxm, arr[ptr2] - check + 1)
			maxm = max(maxm, arr[ptr2] - check)
			ptr1 += 1
			check = arr[ptr1]
		ptr2 += 1
	if arr[-1] < b:
		maxm = max(maxm, b - check + 1)
	print(maxm)


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)


import sys
from math import gcd, sqrt, ceil
from collections import defaultdict, Counter, deque
from bisect import bisect_left, bisect_right
import math
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_sum(bit, i):
	s = 0
	i += 1
	while i > 0:
		s += bit[i]
		i -= i & -i
	return s

def update(bit, n, i, v):
	i += 1
	while i <= n:
		bit[i] += v
		i += i & -i

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def primeFactors(n):
	sa = set()
	sa.add(n)
	while n % 2 == 0:
		sa.add(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			sa.add(i)
			n = n // i
	return sa

def seive(n):
	pri = [True] * (n + 1)
	p = 2
	while p * p <= n:
		if pri[p] == True:
			for i in range(p * p, n + 1, p):
				pri[i] = False
		p += 1
	return pri

def ifposs(l):
	i = a
	while b - i + 1 >= l:
		z = i + l - 1
		if pre[z] - pre[i - 1] < k:
			return False
		else:
			i += 1
	return True
(a, b, k) = map(int, input().split())
pri = []
h = seive(b + 1)
h[1] = False
pre = [0]
for i in range(a, b + 1):
	if h[i] == True:
		pri.append(i)
		pre.append(pre[-1] + 1)
	else:
		pre.append(pre[-1])
pre = [0] * (a - 1) + pre
if len(pri) < k:
	print(-1)
else:
	i = j = a
	l = 0
	while j <= b:
		if pre[j] - pre[i - 1] < k:
			j += 1
		else:
			l = max(l, j - i + 1)
			i += 1
	l = max(l, j - i + 1)
	print(l)


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
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
r = q[qr - 1] - a
while i <= b:
	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:
	r = max(r, b - q[ql - 1] - 1)
else:
	r = max(r, b - q[ql - 1])
print(r + 1)


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)


p1000 = [2, 3, 5, 7, 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, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
sieve = [True] * 1000001
for i in p1000:
	for j in range(2 * i, 1000001, i):
		sieve[j] = False
k = [0] * 1000001
for i in range(2, 1000001):
	if sieve[i]:
		k[i] = k[i - 1] + 1
	else:
		k[i] = k[i - 1]

def primes(a, b):
	return k[b] - k[a - 1]
(a, b, kk) = list(map(int, input().split(' ')))
lo = 0
hi = 1000000
while lo < hi:
	mid = (lo + hi) // 2
	ok = True
	for x in range(a, b - mid + 2):
		if primes(x, x + mid - 1) < kk:
			ok = False
	if ok:
		hi = mid
	else:
		lo = mid + 1
if primes(a, b) < kk:
	print(-1)
else:
	print(lo)


import sys
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def read():
	zz = 0
	if zz:
		input = sys.stdin.readline
	else:
		sys.stdin = open('input1.txt', 'r')
		sys.stdout = open('output1.txt', 'w')
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def solve():
	n = 1000005
	sieve = [1] * 1000005
	(sieve[0], sieve[1]) = (0, 0)
	for i in range(2, int(sqrt(n))):
		if sieve[i]:
			for j in range(i * i, n, i):
				sieve[j] = 0
	for i in range(1, n):
		sieve[i] += sieve[i - 1]

	def check(m):
		for i in range(a, b - m + 2):
			x = sieve[i + m - 1] - sieve[i - 1]
			if x < k:
				return 0
		return 1

	def bs(r):
		l = 1
		ans = -1
		while l <= r:
			m = l + (r - l) // 2
			if check(m):
				ans = m
				r = m - 1
			else:
				l = m + 1
		return ans
	global a, b, k
	(a, b, k) = mi()
	ans = bs(b - a + 1)
	print(ans)
solve()


import os
import sys
from io import BytesIO, IOBase
from bisect import *

def seieve_prime_factorisation(n):
	(p, i) = ([1] * (n + 1), 2)
	while i * i <= n:
		if p[i]:
			for j in range(i * i, n + 1, i):
				p[j] = 0
		i += 1
	p[0] = p[1] = 0
	return p

def check(p, l, a, b, k):
	z = 0
	for i in range(a, a + l):
		z += p[i]
	if z < k:
		return 0
	for i in range(a + l, b + 1):
		z += p[i]
		z -= p[i - l]
		if z < k:
			return 0
	return 1

def main():
	(a, b, k) = map(int, input().split())
	p = seieve_prime_factorisation(b)
	(lo, hi, l) = (0, b - a + 1, -1)
	while lo <= hi:
		mid = (lo + hi) // 2
		if check(p, mid, a, b, k):
			l = mid
			hi = mid - 1
		else:
			lo = mid + 1
	print(l)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import stdin

def main():
	(a, b, k) = map(int, stdin.readline().split())
	check = [True] * (10 ** 6 + 1)
	check[1] = False
	check[0] = False
	index = 2
	bound = 10 ** 6
	while index * index <= bound:
		if check[index]:
			for i in range(index * index, bound + 1, index):
				check[i] = False
		index += 1
	dp = [0] * (bound + 1)
	for i in range(2, bound + 1):
		if check[i]:
			dp[i] = dp[i - 1] + 1
		else:
			dp[i] = dp[i - 1]
	low = 0
	high = b - a + 2
	while low < high:
		mid = low + high >> 1
		ok = True
		for i in range(a, b - mid + 2):
			if dp[i + mid - 1] - dp[i - 1] < k:
				ok = False
				break
		if ok:
			high = mid
		else:
			low = mid + 1
	print(low if low <= b - a + 1 else -1)
main()


(a, b, k) = list(map(int, input().split()))
c = [1] * b
c[0] = 0
for i in range(1, b):
	if c[i]:
		for j in range(2 * i + 1, b, i + 1):
			c[j] = 0
l = -1
(i, j) = (a - 1, a - 2)
x = 0
m = b + 1
while j < b:
	if x < k:
		j += 1
		if j < b:
			x += c[j]
	elif x == k:
		m = i
		l = max(l, j - i + 1)
		x -= c[i]
		i += 1
l = max(l, b - m)
print(l)


(a, b, k) = map(int, input().split())
prime = [True] * (b + 1)
p = []
for i in range(2, b + 1):
	if prime[i]:
		if i >= a:
			p.append(i)
		for j in range(i, b + 1, i):
			prime[j] = False
if len(p) < k:
	print(-1)
else:
	arr1 = [p[i] - p[i - k] for i in range(k, len(p))]
	arr2 = [b - p[-k] + 1, p[k - 1] - a + 1]
	arr = arr1 + arr2
	print(max(arr))


from sys import stdin, stdout
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))
N = 10 ** 6 + 6
primes = [1] * N
p = 2
while p * p <= N:
	if primes[p]:
		for j in range(p * p, N, p):
			primes[j] = 0
	p += 1
primes[1] = primes[0] = 0

def fn(x):
	for i in range(n - x + 1):
		ones = aa[i + x - 1] - (aa[i - 1] if i >= 1 else 0)
		if ones < k:
			return False
	return True
for _ in range(1):
	(a, b, k) = lst()
	n = b - a + 1
	l = 1
	r = b - a + 1
	aa = [0] * (b - a + 1)
	c = 0
	for i in range(a, b + 1):
		aa[c] = primes[i] + aa[max(0, c - 1)]
		c += 1
	while l <= r:
		mid = l + r >> 1
		if fn(mid) == False:
			l = mid + 1
		else:
			r = mid - 1
	print(l if l <= n else -1)