#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int lp[N + 1];
vector<int> pr;
int i, j, p1, p2, x0, x1, x2, ans;
int main() {
  for (i = 2; i <= N; i++) {
    if (lp[i] == 0) {
      lp[i] = i;
      pr.push_back(i);
    }
    for (j = 0; j < pr.size() && pr[j] <= lp[i] && i * pr[j] <= N; j++)
      lp[i * pr[j]] = pr[j];
  }
  cin >> x2;
  for (i = pr.size() - 1; i >= 0; i--)
    if (x2 % pr[i] == 0) break;
  if (x2 == pr[i]) {
    cout << x2 << endl;
    return 0;
  }
  p2 = pr[i];
  ans = x2 - p2 + 1;
  for (j = 0; j < pr.size() && pr[j] <= x2; j++) {
    p1 = pr[j];
    x1 = ((x2 - p2) / p1 + 1) * p1;
    if (x1 > x2) continue;
    if (x1 == p1)
      x0 = p1;
    else
      x0 = x1 - p1 + 1;
    if (x0 >= 3) ans = min(ans, x0);
  }
  cout << ans << endl;
  return 0;
}
