#include <bits/stdc++.h>
using namespace std;
template <class T>
void cmax(T &a, T b) {
  a = (a > b ? a : b);
}
template <class T>
void cmin(T &a, T b) {
  a = (a > b ? b : a);
}
template <class T>
void swp(T &a, T &b) {
  T temp = a;
  a = b;
  b = temp;
}
const long long maxn = 1100000;
long long f[maxn], no[maxn], n, pri_cnt;
long long cl(long long x) {
  long long i;
  for (i = 2; i * i <= x; i++) {
    while (!(x % i)) x /= i;
    if (x == 1) return i;
  }
  return x;
}
int main() {
  scanf("%lld", &n);
  long long i, ans;
  long long temp = cl(n);
  {}
  ans = LLONG_MAX >> 1;
  for (i = n - temp + 1; i <= n; i++) {
    long long temp;
    cmin(ans, (temp = cl(i)) != i ? i - temp + 1 : LLONG_MAX >> 1);
  }
  printf("%lld", ans);
  return 0;
}
