#include <bits/stdc++.h>
using namespace std;
const int OO = 1000 * 1000 * 1000 + 7;
int mini = OO;
int gPrime(int m) {
  int lst = 0;
  int M = m;
  for (int i = 2; i * i <= m; i++) {
    if (m % i == 0) {
      lst = i;
      while (m % i == 0) m /= i;
    }
  }
  if (m > 1 && M != m) lst = m;
  return lst;
}
int main() {
  int n;
  cin >> n;
  int m = n - gPrime(n) + 1;
  for (int i = m; i <= n; i++) {
    mini = min(mini, i - gPrime(i) + 1);
  }
  cout << mini << endl;
}
