#include <bits/stdc++.h>
using namespace std;
inline void init() {}
const int INF = 0x3f3f3f3f;
const int N = 1000005;
int sieve[N];
int main() {
  init();
  for (int i = 2; i < N; i++) {
    if (!sieve[i]) {
      for (int j = i + i; j < N; j += i) sieve[j] = true;
    }
  }
  int x2;
  cin >> x2;
  set<int> sx1;
  for (int i = 2; i * i <= x2; i++) {
    if (x2 % i == 0) {
      int j = 0;
      if (!sieve[i]) j = i;
      if (!sieve[x2 / i]) j = max(j, x2 / i);
      int start = x2;
      if (start == j) {
        sx1.insert(start);
      } else {
        while (start > x2 - j) {
          sx1.insert(start--);
        }
      }
    }
  }
  int l = INF;
  int r = 0;
  int ans = INF;
  for (int x1 : sx1) {
    for (int i = 2; i * i <= x1; i++) {
      if (x1 % i == 0) {
        int j = 0;
        if (!sieve[i]) j = i;
        if (!sieve[x1 / i]) j = max(j, x1 / i);
        int start = x1;
        if (start == j) {
          if (start >= 3) {
            ans = min(ans, start);
            l = min(l, start);
            r = max(r, start);
          }
        } else {
          start = min(start, l);
          while (start > x1 - j) {
            if (start >= 3) {
              ans = min(ans, start);
              l = min(l, start);
              r = max(r, start);
            }
            start--;
          }
        }
      }
    }
  }
  cout << ans << '\n';
  return 0;
}
