#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int x2, x1, mp, mn = 0x3f3f3f3f;
int GetMP(int x) {
  int x1 = 1, x2 = x;
  for (register int i = 2; i <= x; ++i) {
    x1 = i;
    while (x % i == 0) x /= i;
  }
  return x1 == x2 ? -0x3f3f3f3f : x1;
}
int main() {
  scanf("%d", &x2), x1 = x2 - GetMP(x2);
  for (register int i = (x1 + 1); i <= x2; ++i) {
    mn = min(i - (mp = GetMP(i)) + 1, mn);
    if (i / mp == 2) break;
  }
  printf("%d", mn);
  return 0;
}
