#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:20000000")
string problem_name = "a";
void init() { freopen((problem_name + ".in").c_str(), "rt", stdin); }
int mx[1001000];
int main() {
  int x;
  for (int i = 2; i <= 1000000; i++)
    if (mx[i] == 0) {
      int p = i;
      while (p <= 1000000) {
        mx[p] = max(mx[p], i);
        p += i;
      }
    }
  cin >> x;
  int res = x;
  for (int i = x - mx[x] + 1; i <= x; i++)
    if (mx[i] != i) {
      res = min(res, i - mx[i] + 1);
    }
  res = max(res, 3);
  cout << res;
  return 0;
}
