#include <bits/stdc++.h>
using namespace std;
int prim[1000000], pcant = 0;
bool used[1000001];
int main() {
  int X2, X0;
  set<int> X1;
  cin >> X2;
  X0 = X2;
  int aux = X2;
  used[1] = used[0] = true;
  for (int i = 2; i <= 1000000; i++) {
    if (used[i] == 0) {
      prim[pcant] = i;
      pcant++;
      for (int j = i * 2; j <= 1000000; j += i) used[j] = true;
    }
  }
  for (int i = 2; i < X2; i++) {
    if (aux % i == 0) {
      int x1 = X2 - i + 1;
      while (x1 < X2) X1.insert(x1), x1++;
      while (aux % i == 0) aux /= i;
    }
  }
  for (auto k : X1) {
    aux = k;
    if (used[k] == 0)
      X0 = min(aux, X0);
    else
      for (int j = 0; j < pcant && prim[j] < k; j++) {
        int i = prim[j];
        if (aux % i == 0) {
          int x0 = k - i + 1;
          X0 = min(X0, x0);
          while (aux % i == 0) aux /= i;
        }
        if (used[aux] == 0) {
          int x0 = k - aux + 1;
          X0 = min(X0, x0);
          j = pcant + 1;
        }
      }
  }
  cout << X0 << endl;
}
