#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
#pragma GCC optimize("O2")
using namespace std;
void timestamp(char const* const tag, bool absolute = false);
int x2;
void read() { cin >> x2; }
vector<int> get_divs(int x) {
  vector<int> ans;
  for (int d = 2; d * d <= x; ++d) {
    int cnt = 0;
    while (x % d == 0) {
      x /= d;
      ++cnt;
    }
    if (cnt) {
      ans.push_back(d);
    }
  }
  if (x > 1) {
    ans.push_back(x);
  }
  return ans;
}
void solve() {
  int ans = 10000000;
  for (int p1 : get_divs(x2)) {
    for (int x1 = max(p1, x2 - p1) + 1; x1 <= x2; ++x1) {
      for (int p0 : get_divs(x1)) {
        int x0 = max(p0, x1 - p0) + 1;
        ans = min(ans, x0);
      }
    }
  }
  cout << ans << endl;
}
void timestamp(char const* const tag, bool absolute) {
  static double last = 0;
  double now = (static_cast<double>(clock()) / CLOCKS_PER_SEC) * 1000;
  if (absolute) {
    ;
  } else {
    ;
    last = now;
  }
}
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  timestamp("start");
  read();
  timestamp("read()");
  solve();
  timestamp("solve()");
  timestamp("total", true);
  return 0;
}
