#include <bits/stdc++.h>
using namespace std;
set<int> st;
int mx = 1e6 + 10;
void func() {
  bool prime[mx];
  memset(prime, true, sizeof(prime));
  for (int i = 2; i * 1ll * i < mx; i++) {
    if (prime[i]) {
      for (int j = i * 1ll * i; j < mx; j += i) {
        prime[j] = false;
      }
    }
  }
  for (int i = 2; i < mx; i++) {
    if (prime[i]) st.insert(i);
  }
}
int main() {
  int n;
  cin >> n;
  func();
  set<int>::iterator it;
  int li;
  for (it = st.begin(); it != st.end(); it++) {
    if (n % (*it) == 0) {
      li = n - *it + 1;
    }
  }
  int mi = 1e6;
  for (it = st.begin(); it != st.end(); it++) {
    if (*it >= li) {
      mi = min(mi, *it);
    } else {
      int el = *it;
      int id = ceil((li * 1.0) / el);
      int va = id * el;
      if (va <= n) mi = min(mi, va - el + 1);
    }
  }
  cout << mi;
}
