#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-9;
const int INF = 0x7f7f7f7f;
const double PI = acos(-1.0);
template <class T>
inline T gcd(T a, T b) {
  return (b) == 0 ? (a) : gcd((b), ((a) % (b)));
}
template <class T>
inline T lcm(T a, T b) {
  return ((a) / gcd((a), (b)) * (b));
}
template <typename T>
string NumberToString(T Number) {
  ostringstream second;
  second << Number;
  return second.str();
}
struct debugger {
  template <typename T>
  debugger& operator,(const T& v) {
    cerr << v << " ";
    return *this;
  }
} dbg;
bool marked[1000000];
vector<int> primes;
bool isPrime(int n) {
  if (n < 2) return 0;
  if (n == 2) return 1;
  if (n % 2 == 0) return 0;
  return marked[n] == 0;
}
void sieve(int n) {
  primes.push_back(2);
  for (int i = 3; i * i <= n; i += 2) {
    if (marked[i] == 0) {
      primes.push_back(i);
      for (int j = i * i; j <= n; j += i + i) {
        marked[j] = 1;
      }
    }
  }
}
int pre[1000004];
int vag[1000004];
int main() {
  int x2;
  sieve(1000000);
  for (int i = (int)(3); i <= (int)(1000000); i++) {
    int n = i;
    int nn = sqrt(i);
    int mx = -1;
    for (int j = (int)(0); j <= (int)((int)primes.size() - 1); j++) {
      if (primes[j] > nn) break;
      if (n % primes[j] == 0) {
        while (n % primes[j] == 0) n /= primes[j];
        nn = sqrt(n);
        mx = max(mx, primes[j]);
      }
    }
    if (n != 1) mx = max(mx, n);
    vag[i] = mx;
  }
  for (int i = (int)(3); i <= (int)(1000000); i++) {
    if (isPrime(i) == 1) {
      pre[i] = i;
      continue;
    }
    int mn = INF;
    int kk = vag[i];
    int l = ((i / kk) - 1) * kk + 1;
    mn = l;
    pre[i] = mn;
  }
  while (~scanf("%d", &x2)) {
    int xx2 = sqrt(x2);
    int mnx0 = INF;
    int tx2 = x2;
    for (int i = 0; i < primes.size(); i++) {
      if (primes[i] > xx2) break;
      if (x2 % primes[i] == 0) {
        int l = ((tx2 / primes[i]) - 1) * primes[i] + 1;
        int r = tx2 - 1;
        for (int x1 = l; x1 <= r; x1++) {
          if (x1 < 3) continue;
          mnx0 = min(mnx0, pre[x1]);
        }
        while (x2 % primes[i] == 0) x2 /= primes[i];
        xx2 = sqrt(x2);
      }
    }
    if (x2 != 1) {
      int l = ((tx2 / x2) - 1) * x2 + 1;
      int r = tx2 - 1;
      for (int x1 = l; x1 <= r; x1++) {
        if (x1 < 3) continue;
        mnx0 = min(mnx0, pre[x1]);
      }
    }
    printf("%d\n", mnx0);
  }
  return 0;
}
