#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e6 + 3;
int sieve[N] = {0};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  for (int i = 2; i < N; ++i) {
    if (sieve[i] == 0) {
      sieve[i] = i;
      int start = i + i;
      while (start < N) {
        sieve[start] = i;
        start += i;
      }
    }
  }
  int right;
  cin >> right;
  int left = right - sieve[right] + 1;
  int ans = right;
  for (int i = left; i <= right; ++i) {
    int j = i - sieve[i] + 1;
    if (j >= 3) {
      ans = min(ans, j);
    }
  }
  cout << ans << "\n";
  return 0;
}
