B. Primal Sport

Codeforces

IDCF948B

Time1000ms

Memory256MB

Difficulty—

brute forcemathnumber 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[Xi]。注意，如果所选质数 #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, X_1, X_2 \in \mathbb{Z} $ be the state of the game after 0, 1, and 2 turns, respectively. Let $ \mathbb{P} $ denote the set of prime numbers. **Constraints** 1. $ X_2 \in \mathbb{Z} $, $ 4 \leq X_2 \leq 10^6 $, and $ X_2 $ is composite. 2. $ X_0 \geq 3 $. 3. For $ i \in \{1, 2\} $: - There exists a prime $ p_i < X_{i-1} $ such that $$ X_i = \min \{ m \geq X_{i-1} \mid p_i \mid m \} $$ - Equivalently, $ X_i = \left\lceil \frac{X_{i-1}}{p_i} \right\rceil \cdot p_i $ **Objective** Find the minimum possible value of $ X_0 $ such that there exist primes $ p_1, p_2 $ with $ p_1 < X_0 $, $ p_2 < X_1 $, and the above recurrence yields the given $ X_2 $.

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "B. 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": "CF948B"
  },
  "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, X_1, X_2 \\in \\mathbb{Z} $ be the state of the game after 0, 1, and 2 turns, respectively.  \nLet $ \\mathbb{P} $ denote the set of prime numbers.\n\n**Constraints**  \n1. $ X_2...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments