#include <bits/stdc++.h>
using namespace std;
const long long int inf = LLONG_MAX;
int M = 1e9 + 7;
bool vowel(char ch) {
  if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ||
      ch == 'y')
    return 1;
  return 0;
}
int n, a[1000005];
vector<int> f[1000005];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cerr.tie(0);
  cin >> n;
  for (long long int i = 2; i <= 1000000; i++) {
    if (!f[i].empty()) continue;
    for (int j = i; j <= 1000000; j += i) {
      f[j].push_back(i);
    }
  }
  int t = n;
  for (auto i : f[n]) {
    int tmp = n / i;
    for (int j = max(3, tmp * i - i + 1); j <= tmp * i; j++) {
      int t2 = n;
      if (f[j].size() == 1 && f[j][0] == j && j != 3) continue;
      for (auto it : f[j]) {
        int t1 = j / it;
        if (t1 == 1)
          t2 = min(t1 * it, t);
        else
          t2 = min(t2, (t1 - 1) * it + 1);
      }
      t = min(t, t2);
    }
  }
  cout << t << endl;
  return 0;
}
