#include <bits/stdc++.h>
using namespace std;
long long gpf(long long n) {
  long long maxprm = -1, i;
  while (n % 2 == 0) {
    maxprm = 2;
    n >>= 1;
  }
  for (i = 3; i * i <= n; i += 2) {
    while (n % i == 0) {
      maxprm = i;
      n = n / i;
    }
  }
  if (n > 2) maxprm = n;
  return maxprm;
}
int main() {
  long long n, i, j, k, x, y, ans = 9999999999, p, q, r;
  scanf("%lld", &n);
  k = n;
  x = gpf(n);
  y = k - x + 1;
  for (j = y; j <= k; j++) {
    p = j;
    q = gpf(p);
    r = j - q + 1;
    if (r == 1) r = j;
    if (r < ans) ans = r;
  }
  printf("%lld\n", ans);
  return 0;
}
