#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
const long double PI = acos(-1);
long long sqr(long long a) { return a * a; }
int get(int n) {
  int m = n, ans;
  for (int i = 2; i * i <= n; ++i) {
    if (m % i == 0) ans = i;
    while (m % i == 0) m /= i;
  }
  if (m != 1) ans = m;
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n;
  cin >> n;
  int kek = get(n), ans = n;
  for (int i = (kek != n ? n - kek + 1 : n); i <= n; i++) {
    kek = get(i);
    ans = min(ans, (kek != i ? i - kek + 1 : i));
  }
  cout << ans;
}
