#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int Prime[N + 1];
int n;
void Prepare() {
  Prime[1] = 1;
  for (int p = 2; p <= n; ++p)
    if (Prime[p] == 0)
      for (int j = p; j <= n; j += p) Prime[j] = p;
  for (int p = sqrt(n) + 1; p <= n; ++p)
    if (Prime[p] == 0) Prime[p] = p;
}
void Solve() {
  int prime = Prime[n], result = N;
  for (int i = n - prime + 1; i <= n; ++i)
    if (i != Prime[i]) result = min(result, i - Prime[i] + 1);
  printf("%d", min(result, n - prime + 1));
}
int main() {
  scanf("%d", &n);
  Prepare();
  Solve();
  return 0;
}
