#include <bits/stdc++.h>
using namespace std;
int sqr(int a) { return a * a; }
int main() {
  const int MAX = 1e6;
  vector<vector<int> > prime_divs(MAX + 1);
  for (int i = 2; i <= MAX; ++i) {
    if (prime_divs[i].size()) {
      continue;
    }
    for (int j = i; j <= MAX; j += i) {
      prime_divs[j].push_back(i);
    }
  }
  int x2, x0 = MAX + 1;
  cin >> x2;
  for (int pd2 : prime_divs[x2]) {
    for (int x1 = max(pd2, x2 - pd2) + 1; x1 < x2 + 1; ++x1) {
      for (int pd1 : prime_divs[x1]) {
        if (pd1 < x1) {
          x0 = min(x0, max(pd1, x1 - pd1) + 1);
        }
      }
    }
  }
  assert(x0 <= MAX);
  cout << x0;
  return 0;
}
