A. Primal Sport

Codeforces

IDCF947A

Time1000ms

Memory256MB

Difficulty—

brute forcemathnumber theory

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.

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": "CF947A"
  },
  "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"
    }
  ]
}

Full JSON Raw Segments