#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> all_primes;
vector<bool> is_prime(1000001, true);
ll find_max_prime(ll x) {
  for (int i = 2; i * i <= x; ++i) {
    while (x % i == 0) x /= i;
    if (x == 1) return i;
    if (is_prime[x]) return x;
  }
}
ll find_min_num(ll x) {
  ll prime = find_max_prime(x);
  return x - prime + 1;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  for (int i = 2; i < 1000001; ++i) {
    if (is_prime[i]) {
      all_primes.push_back(i);
      for (int j = i + i; j <= 1000000; j += i) is_prime[j] = false;
    }
  }
  all_primes.push_back(1000000007);
  ll ans = 1000000000000000;
  ll x;
  cin >> x;
  ll prime = find_max_prime(x);
  for (ll prev = x - prime + 1; prev <= x; ++prev)
    if (!is_prime[prev]) ans = min(ans, find_min_num(prev));
  cout << ans << "\n";
  return 0;
}
