#include <bits/stdc++.h>
using namespace std;
int MIN_X = 3;
vector<bool> get_primes(long long n) {
  vector<bool> p(n + 1, true);
  p[0] = false;
  p[1] = false;
  for (long long div = 2; div * div <= n; ++div) {
    if (!p[div]) {
      continue;
    }
    for (long long m = div * div; m <= n; m += div) {
      p[m] = false;
    }
  }
  return p;
}
vector<int> all_prime_divisors(int n, const vector<bool> &prime) {
  vector<int> res;
  res.reserve(int(ceil(sqrt(n)) * 2));
  for (int q = 2; q * q <= n; ++q) {
    if (n % q == 0) {
      if (prime[q]) {
        res.push_back(q);
      }
      if (prime[n / q]) {
        res.push_back(n / q);
      }
    }
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int x2;
  cin >> x2;
  auto prime = get_primes(x2 + 1);
  auto x2_divs = all_prime_divisors(x2, prime);
  int min_x1 = x2;
  for (int d : x2_divs) {
    min_x1 = min(min_x1, max(x2 - d + 1, d + 1));
  }
  min_x1 = max(min_x1, MIN_X);
  int min_x0 = x2;
  for (int x1 = min_x1; x1 <= x2; ++x1) {
    if (prime[x1]) {
      continue;
    }
    auto x1_divs = all_prime_divisors(x1, prime);
    for (int d : x1_divs) {
      min_x0 = min(min_x0, max(d + 1, x1 - d + 1));
    }
  }
  min_x0 = max(min_x0, MIN_X);
  cout << min_x0 << endl;
  return 0;
}
