#include <bits/stdc++.h>
clock_t t_;
using namespace std;
vector<int> uq;
vector<int> pr;
const int maxn = 1000010 * 4;
int p[maxn], hi[maxn];
int ans = 1000000000;
void fact(int n) {
  int pp = 0;
  while (n > 1) {
    if (n % pr[pp] == 0) {
      uq.push_back(pr[pp]);
    }
    while (n % pr[pp] == 0) {
      n /= pr[pp];
    }
    pp++;
  }
}
void prec(int n) {
  for (int i = int(2); i < int(n + 1); i++) {
    int pp = 0;
    int ret = i;
    while (!p[ret] && ret > 1) {
      while (!p[ret] && ret % pr[pp] == 0) {
        ret /= pr[pp];
      }
      pp++;
    }
    hi[i] = ret;
  }
}
void act(int highestPR, int number) {
  if (highestPR == number && highestPR >= 3) {
    ans = min(ans, highestPR);
    return;
  }
  if (number - (highestPR - 1) >= 3) ans = min(ans, number - (highestPR - 1));
}
int main(int argc, const char* argv[]) {
  t_ = clock();
  int n;
  cin >> n;
  memset(p, 1, sizeof(p));
  p[0] = p[1] = false;
  for (int i = 2; i <= n; i++) {
    if (p[i]) {
      pr.push_back(i);
      for (int j = i * 2; j <= n; j += i) {
        p[j] = false;
      }
    }
  }
  fact(n);
  prec(n);
  for (int i = int(0); i < int(uq.size()); i++) {
    int j = 0;
    while (j < uq[i]) {
      act(hi[n - j], n - j);
      j++;
    }
  }
  cout << ans << endl;
  t_ = clock() - t_;
  cerr << setprecision(9) << fixed << ((float)t_ / CLOCKS_PER_SEC) << endl;
  return 0;
}
