#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000009;
const long long INF = 1e9 + 5;
const double eps = 1e-7;
const double PI = acos(-1.0);
inline void debug_vi(vector<int> a) {
  for (long long i = (long long)(0); i < (long long)(a.size()); i++)
    cout << a[i] << " ";
}
inline void debug_vll(vector<long long> a) {
  for (long long i = (long long)(0); i < (long long)(a.size()); i++)
    cout << a[i] << " ";
}
inline void print_case(int tn) { cout << "Case #" << tn << ": "; }
template <typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using maxpq = priority_queue<T>;
const int MAXN = 1000005;
int spf[MAXN];
void sieve() {
  spf[1] = 1;
  for (int i = 2; i < MAXN; i++) spf[i] = i;
  for (int i = 4; i < MAXN; i += 2) spf[i] = 2;
  for (int i = 3; i * i < MAXN; i++) {
    if (spf[i] == i) {
      for (int j = i * i; j < MAXN; j += i)
        if (spf[j] == j) spf[j] = i;
    }
  }
}
set<int> getFactorization(int x) {
  set<int> ret;
  while (x != 1) {
    ret.insert(spf[x]);
    x = x / spf[x];
  }
  return ret;
}
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int x2;
  cin >> x2;
  sieve();
  int res = INF;
  auto pf = getFactorization(x2);
  for (long long x1 = (long long)(3); x1 < (long long)(x2 + 1); x1++) {
    auto pf2 = getFactorization(x1);
    for (int p : pf) {
      if (p > x1) break;
      int val = x1 / p;
      bool good = false;
      if (p * val == x1 && x1 == x2)
        good = true;
      else if (p * val != x1 && (val + 1) * p == x2)
        good = true;
      if (good) {
        for (int p2 : pf2) {
          if (p2 == x1) continue;
          res = min(res, (int)x1 - p2 + 1);
        }
      }
    }
  }
  cout << res;
  return 0;
}
