← 返回题目列表

Codeforces · 237/C

C. 间隔素数

中文机器翻译题面 查看原题

您决定进行素数理论调查。让我们提醒您,素数是具有两个不同正整数除数的正整数。

考虑正整数 a、a + 1、...、b (a ≤ b)。您想要找到最小整数 l (1 ≤ l ≤ b - a + 1),使得对于 l 个整数 x, x + 1, ..., x + l - 1 中的任何整数 x (a ≤ x ≤ b - l + 1) 至少有 k 个素数。

查找并打印所需的最小 l。如果没有值 l 满足所描述的限制,则打印 -1。

输入

单行包含三个空格分隔的整数 a、b、k(1 ≤ a、b、k ≤ 106;a ≤ b)。

输出

在一行中打印一个整数 - 所需的最小 l。如果无解,则打印-1。

示例

输入 #1

2 4 2

输出 #1

3

输入 #2

6 13 1

输出 #2

4

输入 #3

1 4 3

输出 #3

-1