← 返回题目列表

Codeforces · 923/A

A. 原始运动

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

Alice 和 Bob 以一场快速游戏开始他们的一天。他们首先选择一个起始数字 X0 ≥ 3,并尝试通过下面描述的过程达到 100 万。

Alice 先走,然后他们交替轮流。在第i回合中,轮到的玩家选择一个小于当前数字的素数,并宣布该素数的不小于当前数字的最小倍数。

正式地,他或她选择一个素数 p < Xi - 1,然后找到最小的 Xi ≥ Xi - 1,使得 p 除 Xi。请注意,如果所选素数 p 已整除 Xi - 1,则该数字不会改变。

Eve在两回合后见证了游戏的状态。给定 X2,帮助她确定最小的可能起始数 X0。请注意,玩家不一定会发挥最佳状态。您应该考虑所有可能的游戏演变。

输入

输入包含单个整数 X2 (4 ≤ X2 ≤ 106)。保证整数X2是合数,即不是素数。

输出

输出一个整数——可能的最小 X0。

示例

输入 #1

14

输出 #1

6

输入 #2

20

输出 #2

15

输入 #3

8192

输出 #3

8191

注意

在第一个测试中,最小可能的起始数字是 X0 = 6。游戏的一个可能的过程如下:

- Alice 选择素数 5 并宣布 X1 = 10
- Bob 选择素数 7 并宣布 X2 = 14。

在第二种情况下,令 X0 = 15。

- Alice 选择素数 2 并宣布 X1 = 16
- Bob 选择素数 5 并宣布 X2 = 20。