#include <bits/stdc++.h>
using namespace std;
int x, f[1000010], cnt, p[1000010];
template <typename T>
void read(T &x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x *= f;
}
void init() {
  for (int i = 2; i <= x; ++i) {
    if (!f[i]) {
      f[i] = i;
      p[++cnt] = i;
    }
    for (int j = 1; j <= cnt && p[j] <= i; ++j) {
      if (p[j] * i > x) break;
      f[p[j] * i] = f[i];
    }
  }
}
int main() {
  read(x);
  init();
  int ans = x;
  if (f[x] == x) {
    printf("%d\n", x);
    return 0;
  }
  for (int i = x - f[x] + 1; i <= x; ++i) {
    if (f[i] == i)
      ans = min(ans, i);
    else
      ans = min(ans, i - f[i] + 1);
  }
  printf("%d\n", ans);
  return 0;
}
