#include <bits/stdc++.h>
using namespace std;
const int len = 2e6;
int f[len];
bool isprime(long long x) {
  if (f[x] == 1) return true;
  if (f[x] == 2) return false;
  if (x == 1) return false;
  for (long long i = 2; i * i <= x; i++)
    if (x % i == 0) {
      f[x] = 2;
      return false;
    }
  f[x] = 1;
  return true;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  vector<long long> m((int)1e6 + 1);
  for (long long i = 2; i <= 1e6; i++) {
    if (m[i] == 0) {
      m[i] = i;
      for (int j = i + i; j <= 1e6; j += i) {
        m[j] = max(m[j], i);
      }
    }
  }
  long long x;
  cin >> x;
  long long ans = x;
  for (int i = max(m[x] + 1, x - m[x] + 1); i <= x; i++) {
    if (i - m[i] + 1 > m[i]) ans = min(ans, i - m[i] + 1);
  }
  cout << ans;
  cerr << clock() << endl;
}
