A. Primal Sport

Codeforces

IDCF923A

Time1000ms

Memory256MB

Difficulty—

mathnumber theory

English · Original

Chinese · Translation

Formal · Original

Alice and Bob begin their day with a quick game. They first choose a starting number _X_0 ≥ 3 and try to reach one million by the process described below. Alice goes first and then they take alternating turns. In the _i_\-th turn, the player whose turn it is selects a prime number smaller than the current number, and announces the smallest multiple of this prime number that is not smaller than the current number. Formally, he or she selects a prime _p_ < _X__i_ - 1 and then finds the minimum _X__i_ ≥ _X__i_ - 1 such that _p_ divides _X__i_. Note that if the selected prime _p_ already divides _X__i_ - 1, then the number does not change. Eve has witnessed the state of the game after two turns. Given _X_2, help her determine what is the smallest possible starting number _X_0. Note that the players don't necessarily play optimally. You should consider all possible game evolutions. ## Input The input contains a single integer _X_2 (4 ≤ _X_2 ≤ 106). It is guaranteed that the integer _X_2 is composite, that is, is not prime. ## Output Output a single integer — the minimum possible _X_0. [samples] ## Note In the first test, the smallest possible starting number is _X_0 = 6. One possible course of the game is as follows: * Alice picks prime 5 and announces _X_1 = 10 * Bob picks prime 7 and announces _X_2 = 14. In the second case, let _X_0 = 15. * Alice picks prime 2 and announces _X_1 = 16 * Bob picks prime 5 and announces _X_2 = 20.

Alice 和 Bob 以一个快速游戏开始他们的一天。他们首先选择一个起始数字 #cf_span[X0 ≥ 3]，并通过以下过程尝试达到一百万。 Alice 先手，然后两人轮流进行。在第 #cf_span[i] 轮中，轮到的玩家选择一个小于当前数字的质数，并宣布不小于当前数字的该质数的最小倍数。形式上，他或她选择一个质数 #cf_span[p < Xi - 1]，然后找到满足 #cf_span[p] 整除 #cf_span[Xi] 的最小 #cf_span[Xi ≥ Xi - 1]。注意，如果所选质数 #cf_span[p] 已经整除 #cf_span[Xi - 1]，则数字不会改变。 Eve 已经见证了游戏进行两轮后的状态。给定 #cf_span[X2]，帮助她确定最小可能的起始数字 #cf_span[X0]。注意，玩家不一定以最优方式玩。你需要考虑所有可能的游戏演变过程。输入包含一个整数 #cf_span[X2] (#cf_span[4 ≤ X2 ≤ 106])。保证整数 #cf_span[X2] 是合数，即不是质数。输出一个整数 —— 最小可能的 #cf_span[X0]。 ## Input 输入包含一个整数 #cf_span[X2] (#cf_span[4 ≤ X2 ≤ 106])。保证整数 #cf_span[X2] 是合数，即不是质数。 ## Output 输出一个整数 —— 最小可能的 #cf_span[X0]。 [samples] ## Note 在第一个测试中，最小可能的起始数字是 #cf_span[X0 = 6]。一种可能的游戏过程如下： Alice 选择质数 5 并宣布 #cf_span[X1 = 10]； Bob 选择质数 7 并宣布 #cf_span[X2 = 14]。在第二种情况中，设 #cf_span[X0 = 15]： Alice 选择质数 2 并宣布 #cf_span[X1 = 16]； Bob 选择质数 5 并宣布 #cf_span[X2 = 20]。

**Definitions** Let $ X_0 \geq 3 $ be the starting integer. Let $ X_1, X_2 \in \mathbb{Z} $ be the states after Alice’s and Bob’s moves, respectively. **Constraints** 1. $ 4 \leq X_2 \leq 10^6 $, and $ X_2 $ is composite. 2. For $ i \in \{1, 2\} $: - There exists a prime $ p_i $ such that $ p_i < X_{i-1} $. - $ X_i = \min \{ y \geq X_{i-1} \mid p_i \mid y \} $. **Objective** Find the minimum possible value of $ X_0 $ such that there exist primes $ p_1, p_2 $ and integers $ X_1 $ satisfying the above transition rules and $ X_2 $ is given.

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "A. Primal Sport",
    "description": {
      "content": "Alice and Bob begin their day with a quick game. They first choose a starting number _X_0 ≥ 3 and try to reach one million by the process described below. Alice goes first and then they take alternat",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF923A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alice and Bob begin their day with a quick game. They first choose a starting number _X_0 ≥ 3 and try to reach one million by the process described below.\n\nAlice goes first and then they take alternat...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Alice 和 Bob 以一个快速游戏开始他们的一天。他们首先选择一个起始数字 #cf_span[X0 ≥ 3]，并通过以下过程尝试达到一百万。\n\nAlice 先手，然后两人轮流进行。在第 #cf_span[i] 轮中，轮到的玩家选择一个小于当前数字的质数，并宣布不小于当前数字的该质数的最小倍数。\n\n形式上，他或她选择一个质数 #cf_span[p < Xi - 1]，然后找到满足 #cf_spa...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ X_0 \\geq 3 $ be the starting integer.  \nLet $ X_1, X_2 \\in \\mathbb{Z} $ be the states after Alice’s and Bob’s moves, respectively.  \n\n**Constraints**  \n1. $ 4 \\leq X_2 \\leq 10^...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments