#include <bits/stdc++.h>
using namespace std;
int n, ans = 1000000007, temp;
vector<int> pri;
int get(int x) {
  pri.clear();
  for (int i = (2); i <= (sqrt(x)); ++i)
    if (x % i == 0) {
      pri.push_back(i);
      while (x % i == 0) x /= i;
    }
  if (x != 1) pri.push_back(x);
  return pri[pri.size() - 1];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  temp = get(n);
  if (temp == n) {
    cout << n;
    return 0;
  }
  for (int i = (0); i <= (temp - 1); ++i) {
    int qwe = get(n - i);
    if (qwe == n - i)
      ans = min(ans, qwe);
    else
      ans = min(ans, n - i - qwe + 1);
  }
  cout << ans;
}
