#include <bits/stdc++.h>
bool vis[1000010];
int n;
void prime() {
  vis[1] = 1;
  for (int i = 2; i <= 1e6; i++)
    if (!vis[i]) {
      for (int j = 2; j * i <= 1e6; j++) vis[j * i] = 1;
    }
}
int maxprie(int x) {
  int sx = (int)sqrt(x);
  int max = -1230;
  for (int i = 2; i <= sx; i++)
    if (x % i == 0) {
      if (!vis[i]) max = std::max(max, i);
      if (!vis[x / i]) max = std::max(max, x / i);
    }
  return max;
}
int main() {
  prime();
  scanf("%d", &n);
  int l = n - maxprie(n) + 1;
  int min = 0x5f5f5f5f;
  for (int i = l; i <= n; i++)
    if (!vis[i])
      min = std::min(min, i);
    else
      min = std::min(min, i - maxprie(i) + 1);
  printf("%d", min);
  return 0;
}
