#include <bits/stdc++.h>
using namespace std;
bool prime(int n) {
  int i;
  if (n % 2 == 0) return 0;
  for (i = 3; i * i <= n; i += 2)
    if (n % i == 0) return 0;
  return 1;
}
int fac(int n) {
  int i, ans = -1;
  if (n % 2 == 0) {
    ans = 2;
    if (prime(n / 2)) ans = max(ans, n / 2);
  }
  for (i = 3; i * i <= n; i++) {
    if (n % i == 0 && prime(i)) ans = max(i, ans);
    if (n % i == 0 && prime(n / i) && i * i != n) ans = max(ans, n / i);
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  int i, n, x, p, ans = -1, l;
  cin >> n;
  p = fac(n);
  int s = n - p + 1;
  int g = fac(s);
  ans = s - g + 1;
  for (i = s + 1; i <= n; i++) {
    l = fac(i);
    if (l == -1) continue;
    ans = min(ans, i - l + 1);
  }
  cout << ans << endl;
}
