#include <bits/stdc++.h>
using namespace std;
const int inf = (int)1e9;
const long long INF = (long long)1e18;
const double eps = 1e-9;
const double pi = acos(-1.0);
const int N = 100100;
int p[1000100], n;
int ans[1000100], t[4000400];
void upd(int tl, int tr, int pos, int val, int v) {
  if (tl == tr)
    t[v] = pos;
  else {
    int m = (tl + tr) >> 1;
    if (pos <= m)
      upd(tl, m, pos, val, 2 * v);
    else if (pos > m)
      upd(m + 1, tr, pos, val, v + v + 1);
    if (ans[t[v + v]] < ans[t[v + v + 1]])
      t[v] = t[v + v];
    else
      t[v] = t[v + v + 1];
  }
}
int get(int tl, int tr, int l, int r, int v) {
  if (tl == l && tr == r) return t[v];
  int m = (tl + tr) >> 1;
  if (r <= m)
    return get(tl, m, l, r, v + v);
  else if (l > m)
    return get(m + 1, tr, l, r, v + v + 1);
  int px = get(tl, m, l, m, v + v);
  int py = get(m + 1, tr, m + 1, r, v + v + 1);
  if (ans[px] < ans[py]) return px;
  return py;
}
int main() {
  for (int i = 2; i <= 1000000; ++i) {
    if (!p[i]) {
      for (int j = i + i; j <= 1000000; j += i) {
        p[j] = i;
      }
    }
  }
  cin >> n;
  for (int i = 2; i < n; ++i) {
    if (!p[i])
      ans[i] = i;
    else
      ans[i] = get(1, n, i - p[i] + 1, i - 1, 1);
    if (i - p[i] + 1 > p[i]) ans[i] = min(ans[i], i - p[i] + 1);
    upd(1, n, i, ans[i], 1);
  }
  cout << ans[get(1, n, n - p[n] + 1, n - 1, 1)] << endl;
  return 0;
}
