#include <bits/stdc++.h>
int a[2000005];
void get(int x2) {
  for (int i = 2; i < x2; i++)
    if (!a[i]) {
      int u = 0;
      for (int j = 2; u <= x2; j++) {
        u = i * j;
        a[u] = i;
      }
    }
}
int main() {
  int x2;
  while (scanf("%d", &x2) == 1) {
    memset(a, 0, sizeof(a));
    get(x2);
    int min = 0x3f3f3f3f;
    for (int i = x2 - a[x2] + 1; i <= x2; i++) {
      if (i - a[i] + 1 < min) min = i - a[i] + 1;
    }
    printf("%d\n", min);
  }
  return 0;
}
