#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
inline long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 1) + (x << 3) + (ch ^ 48);
    ch = getchar();
  }
  return x * f;
}
long long die = 0;
const double eps = 1e-9;
const long long mod = 1e9 + 7;
const long long N = 1e6 + 5;
long long x2, x1, x0;
long long mx(long long x) {
  long long ret = 0;
  for (long long i = (2); i <= (sqrt(x)); i++) {
    if (x % i == 0) {
      ret = i;
      while (x % i == 0) x /= i;
    }
  }
  if (x > 1) ret = x;
  return ret;
}
void sol1() {
  long long ans = inf;
  long long low = x2 + 1 - mx(x2);
  for (long long x1 = (low); x1 <= (x2); x1++) {
    x0 = x1 + 1 - mx(x1);
    if (x0 == 1) continue;
    ans = min(x0, ans);
  }
  cout << ans;
}
void rd() { x2 = read(); }
signed main() {
  rd();
  sol1();
}
