#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-9;
const int maxn = 1e6 + 10;
int main() {
  vector<bool> prime(maxn + 1, true);
  vector<int> primes;
  prime[0] = prime[1] = false;
  for (int i = 2; i <= maxn; i++) {
    if (!prime[i]) continue;
    primes.push_back(i);
    if (i * 1LL * i <= maxn) {
      for (int j = i * i; j <= maxn; j += i) {
        prime[j] = false;
      }
    }
  }
  int x2;
  cin >> x2;
  vector<int> x2primes;
  for (int i = 2; i * i <= x2; i++) {
    if (prime[i] && x2 % i == 0) x2primes.push_back(i);
    if (x2 % i == 0 && prime[x2 / i]) x2primes.push_back(x2 / i);
  }
  int result = INT_MAX;
  for (int pr : x2primes) {
    for (int x1 = x2 - pr + 1; x1 <= x2; x1++) {
      int mx = 0;
      for (int i = 2; i * i <= x1; i++) {
        if (x1 % i == 0) {
          if (prime[i]) mx = i;
          if (prime[x1 / i]) {
            mx = x1 / i;
            break;
          }
        }
      }
      result = min(result, max(3, x1 - mx + 1));
    }
  }
  cout << result << '\n';
  return 0;
}
