Dotcpp  >  编程题库  >  蓝桥杯2022年第十三届决赛真题-选素数
题目 2712:

蓝桥杯2022年第十三届决赛真题-选素数

时间限制: 1s 内存限制: 256MB 提交: 69 解决: 17

题目描述

小蓝有一个数 x,每次操作小蓝会选择一个小于 x 的素数 p,然后在 x 成为 p 的倍数前不断将 x 加 1,(如果 x 一开始就是 p 的倍数则 x 不变)。

小乔看到了小蓝进行了 2 次上述操作后得到的结果 n,他想知道 x 在一开始是多少。如果有多种可能,他想知道 x 一开始最小可以是多少,而如果不存在任何解,说明小乔看错了,此时请输出 −1。

输入格式

输入一行包含一个整数 n ,表示经过两次操作后 x 的值。

输出格式

输出一行包含一个整数表示 x 的初始值。如果有多个解,输出最小的。如果不存在解,请输出 −1 。

样例输入

22

样例输出

8

提示

对于 60% 的评测用例,1 ≤ n ≤ 5000;

对于所有评测用例,1 ≤ n ≤ 106

标签