#include <bits/stdc++.h>
using namespace std;
const long long N = 1e6 + 5;
vector<long long> p;
bool u[N];
long long x;
void eratos() {
  for (long long i = 2; i * i <= N; ++i)
    if (not u[i]) {
      p.push_back(i);
      for (long long j = 2 * i; j < N; j += i) u[j] = true;
    }
}
long long low(long long x) {
  vector<long long> v;
  v.clear();
  long long a = x;
  for (long long i = 0; p[i] * p[i] <= x; ++i) {
    if (i == p.size()) break;
    if (x % p[i] == 0) {
      while (a % p[i] == 0) a /= p[i];
      v.push_back(p[i]);
    }
  }
  if (a > 1) v.push_back(a);
  if (a == x) return 1e9 + 7;
  return x - v.back() + 1;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  eratos();
  cin >> x;
  long long ans = 1e9 + 7;
  for (long long i = low(x); i <= x; ++i) {
    ans = min(ans, low(i));
  }
  cout << ans;
}
