#include <bits/stdc++.h>
using namespace std;
const int S = 1e6 + 9;
int sv[S];
void sieve() {
  for (int i = 2; i < S; i++) sv[i] = i;
  for (int i = 2; i < S; i++)
    if (sv[i] == i)
      for (int j = i << 1; j < S; j += i) sv[j] = i;
}
int x, n;
int main() {
  sieve();
  cin >> x;
  n = x;
  set<int> c;
  while (x > 1) {
    int p = sv[x];
    int cnt = 0;
    while (x % p == 0) x /= p, cnt++;
    if (cnt) {
      int lb = n - (p - 1), ub = n;
      for (int i = lb; i <= ub; i++) c.insert(i);
    }
  }
  int mn = S;
  for (int i : c) {
    if (sv[i] == i) continue;
    int copy = i;
    while (copy > 1) {
      int p = sv[copy];
      int cnt = 0;
      while (copy % p == 0) copy /= p, cnt++;
      if (cnt) mn = min(mn, i - p + 1);
    }
  }
  cout << mn << '\n';
}
