#include <bits/stdc++.h>
using namespace std;
const long long md = 1e9 + 7;
const int MX = 1e6 + 1;
int ans = 1e9;
vector<vector<int>> dv(MX);
vector<vector<int>> us(MX, vector<int>(3, 0));
void bfs(int v, int d) {
  if (us[v][d]) {
    return;
  }
  us[v][d] = 1;
  if (d == 0) {
    ans = min(ans, v);
    return;
  }
  if (dv[v].empty()) {
    return;
  }
  for (int df : dv[v]) {
    for (int bg = v - df + 1; bg <= v - df + 1; bg++) {
      bfs(bg, d - 1);
    }
  }
  bfs(v, d - 1);
}
int main() {
  iostream::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  for (int i = 2; i < MX; i++) {
    if (dv[i].size()) {
      continue;
    }
    for (int j = i + i; j < MX; j += i) {
      dv[j].push_back(i);
    }
  }
  int fn;
  cin >> fn;
  int mx = 0;
  for (int d : dv[fn]) {
    mx = max(mx, d);
  }
  for (int bg = fn - mx + 1; bg <= fn; bg++) {
    if (dv[bg].empty()) {
      continue;
    }
    int c = 0;
    for (int d : dv[bg]) {
      c = max(c, d);
    }
    ans = min(ans, bg - c + 1);
  }
  cout << ans;
  return 0;
}
