#include <bits/stdc++.h>
using namespace std;
int maxn, ans = 1e6, n;
int main() {
  scanf("%d", &n);
  int t = n, f = 1, qn = sqrt(n);
  while (f <= qn + 1) {
    f++;
    while (t % f == 0) t /= f, maxn = max(maxn, f);
  }
  if (t != 1) maxn = max(maxn, t);
  for (int i = n - maxn + 1; i <= n; i++) {
    int nw = 0;
    int t = i, f = 1, qn = sqrt(i);
    while (f <= qn) {
      f++;
      while (t % f == 0) t /= f, nw = max(nw, f);
    }
    if (t != 1 && nw != 0) nw = max(nw, t);
    ans = min(ans, i - nw + 1);
  }
  printf("%d", ans);
}
