#include <bits/stdc++.h>
using namespace std;
int maxPrimeFactor[1000005];
void sieve(int n) {
  for (int p = 2; p <= n; p++) {
    if (maxPrimeFactor[p] == 0) {
      for (int i = p; i <= n; i += p) {
        maxPrimeFactor[i] = p;
      }
    }
  }
}
int main() {
  sieve(1000000);
  int n;
  scanf("%d", &n);
  int res = n - maxPrimeFactor[n] + 1;
  for (int i = n; i > (n - maxPrimeFactor[n]); i--) {
    if (maxPrimeFactor[i] == i) {
      res = min(res, i);
    } else {
      res = min(res, (i - maxPrimeFactor[i] + 1));
    }
  }
  printf("%d\n", res);
  return 0;
}
