#include <bits/stdc++.h>
using namespace std;
long long lp[1000010];
long long get(long long N) {
  if (!lp[N]) return 1e9;
  return N - lp[N] + 1;
}
signed main() {
  long long N;
  cin >> N;
  for (long long i = 2; i <= N; i++)
    if (!lp[i]) {
      for (long long j = i * 2; j <= N; j += i) {
        lp[j] = i;
      }
    }
  long long ans = 1e9;
  for (long long i = N - lp[N] + 1; i <= N; i++) {
    ans = min(ans, get(i));
  }
  cout << ans << endl;
}
