#include <bits/stdc++.h>
using namespace std;
const long INF = numeric_limits<int>::max();
bool ev[1000005];
int maxPrime[1000005];
int process(int i, int n) {
  int sol = 1000005;
  for (int j = n - i + 1; j <= n; j++)
    if (ev[j]) sol = min(sol, j - maxPrime[j] + 1);
  return sol;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  for (int i = 2; i < 1000005; i++)
    for (int j = 2; i * j < 1000005; j++) ev[i * j] = true;
  fill(maxPrime, maxPrime + 1000005, 1);
  for (int i = 2; i < 1000005; i++)
    if (!ev[i])
      for (int j = 2; j * i < 1000005; j++)
        maxPrime[i * j] = max(maxPrime[i * j], i);
  int n;
  cin >> n;
  int sol = 1000005;
  for (int i = 2; i <= sqrt(n); i++) {
    if (n % i == 0 && !ev[i]) sol = min(sol, process(i, n));
    if (n % i == 0 && !ev[n / i]) sol = min(sol, process(n / i, n));
  }
  cout << sol << endl;
}
