#include <bits/stdc++.h>
using namespace std;
const long long int N = 1e6 + 5, MOD = 1e9 + 7;
float x2;
long long int prime[N];
void precal() {
  for (long long int i = 2; i < N; i++) {
    if (!prime[i]) {
      for (long long int j = i; j < N; j += i) prime[j] = i;
    }
  }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  precal();
  cin >> x2;
  float p1 = prime[(long long int)x2], wt;
  wt = x2 - p1;
  long long int mi = 1e9;
  for (long long int i = wt + 1; i <= x2; i++) {
    if (prime[i] == i) continue;
    mi = min(mi, i - prime[i]);
  }
  mi++;
  cout << mi << endl;
  return 0;
}
