Problem J
Sieve Overflow

Image created using Google ImageFX

You may be familiar with the Sieve of Eratosthenes, which is an ancient Greek algorithm for finding all prime numbers less than or equal to some integer, $n.$ A standard implementation uses an array of length $n,$ with positions indexed $1, 2, \ldots , n.$ Before the algorithm executes, each position contains a constant denoted EMPTY. After the algorithm has finished, each $\textrm{position}~ i$ contains either the constant PRIME, if $i~ \textrm{is}$ prime, or the constant COMPOSITE, if $i~ \textrm{is}$ composite (except for $\textrm{position}~ 1,$ which can be left untouched). The algorithm works by iterating through the array, starting with $i=2,$ and each time $\textrm{position}~ i$ is found to contain EMPTY, it is assigned PRIME, and every other multiple of $i$ is assigned COMPOSITE. This process continues up to and including $i = \left\lfloor \sqrt{n} \right\rfloor $ (where $\left\lfloor ~ \right\rfloor $ is the floor function, which rounds down to the nearest integer), after which any remaining positions containing EMPTY are assigned PRIME. (Additional refinements are possible, but this version is fairly efficient.)

Here is the Sieve of Eratosthenes in pseudocode. For the sake of this problem, we assume $n \geq 4,$ since this guarantees that the first for loop iterates at least once. We use the variable sieve for the array.

      limit = floor(sqrt(n))
      for i = 2 ... limit
          if sieve[i] == EMPTY:
              sieve[i] = PRIME
              multiple = 2*i
              while multiple <= n:
                  sieve[multiple] = COMPOSITE
                  multiple = multiple + i         (**)

      for i = (limit + 1) ... n:
          if sieve[i] == EMPTY:
              sieve[i] = PRIME    

There is a potential issue, though. In many programming languages, each standard integer type can only represent integers up to some maximum, $m.$ Attempting to assign an integer larger than $m$ to a variable of that type will result in overflow. If $n \leq m,$ then most of the above pseudocode is fine, except possibly the line marked (**), which updates the variable multiple. For a given $m,$ an integer $n$ is called sieve-safe if running the above algorithm for $n$ will not result in overflow. Your challenge is to find the largest sieve-safe value of $n.$

For example, suppose $m=7$. If $n=7,$ then multiple will be assigned the values $2, 4, 6, 8,$ the last of which will result in overflow. If $n=6,$ the same thing will happen. If $n=5,$ however, multiple will only be assigned $2, 4, 6$ before the while loop terminates, thereby avoiding overflow, so $5$ is the largest sieve-safe value of $n.$

Input

The input consists of a single integer, $m$ $(6 \leq m \leq 10^{15})$, the maximum value that can be stored in the variable multiple without overflow.

Output

Output a positive integer, the largest sieve-safe value of $n,$ as described above. It is guaranteed that there is at least one sieve-safe value in the interval $[4,m].$

7

5

100

97