#include <bits/stdc++.h>
using namespace std;
int prime[2000000 + 1];
long long p[1000000];
long long n;
void solve() {
  memset(prime, 1, sizeof(prime));
  for (int i = 0; i < 2000001; i++) prime[i] = 1;
  n = 0;
  prime[0] = 0;
  prime[1] = 0;
  for (long long k = 2; k <= 2000000; k++) {
    while (prime[k] > 1) k++;
    p[n++] = k;
    for (long long i = 2 * k; i <= 2000000; i += k) prime[i] = k;
  }
}
int main() {
  solve();
  long long X2;
  scanf("%lld", &X2);
  long long mi;
  for (long long i = 0; i < n; i++) {
    if (p[i] > X2) break;
    if (X2 % p[i] == 0) mi = i;
  }
  long long X1 = X2 - p[mi] + 1;
  long long X0 = 1000000;
  for (long long i = X2; i >= X1; i--) {
    long long tmp = prime[i];
    if (i - tmp + 1 < X0) X0 = i - tmp + 1;
  }
  printf("%lld\n", X0);
  return 0;
}
