#include <bits/stdc++.h>
using namespace std;
int n = 1e6;
vector<int> primes;
vector<int> d(n + 1, -1);
int get_max_prime(int x) {
  if (d[x] == -1) return x;
  int preans = 0;
  while (x != 1) {
    preans = primes[d[x]];
    x /= preans;
  }
  return preans;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  primes.reserve(n);
  for (int y = 2; y <= n; y++) {
    if (d[y] == -1) {
      d[y] = primes.size();
      primes.push_back(y);
    }
    for (int i = 0; i <= d[y] && y * primes[i] <= n; i++) {
      d[y * primes[i]] = i;
    }
  }
  int x2;
  cin >> x2;
  int x0 = INT_MAX;
  int p = primes[d[x2]];
  int rem = x2;
  while (rem > 0) {
    int border = max(x2 - p + 1, p + 1);
    for (int x1 = border; x1 <= x2; x1++) {
      int qopa = get_max_prime(x1);
      x0 = min(x0, max(x1 - qopa + 1, qopa + 1));
    }
    if (rem == 1) {
      rem = 0;
    }
    rem /= p;
    if (d[rem] == -1) {
      p = rem;
    } else
      p = primes[d[rem]];
  }
  cout << x0;
  return 0;
}
