#include <bits/stdc++.h>
using namespace std;
long long _sieve_size = 1000006;
bitset<10000010> bs;
vector<int> primes;
void sieve() {
  bs.set();
  bs[0] = bs[1] = 0;
  for (long long i = 2; i <= _sieve_size; i++)
    if (bs[i]) {
      for (long long j = i * i; j <= _sieve_size; j += i) bs[j] = 0;
      primes.push_back((int)i);
    }
}
bool isPrime(long long N) {
  if (N <= _sieve_size) return bs[N];
  for (int i = 0; i < (int)primes.size(); i++)
    if (N % primes[i] == 0) return false;
  return true;
}
int primeFactors(long long N) {
  vector<int> factors;
  long long PF_idx = 0, PF = primes[PF_idx];
  int ret;
  while (PF * PF <= N) {
    if (N % PF == 0) {
      factors.push_back(PF);
      ret = PF;
      while (N % PF == 0) N /= PF;
    }
    PF = primes[++PF_idx];
  }
  return max(1ll * ret, N);
}
int main() {
  int n;
  scanf("%d", &n);
  sieve();
  int v = primeFactors(n);
  int ans = 100000000;
  for (int i = n; i > n - v; i--) {
    if (isPrime(i)) {
      ans = min(ans, i);
      continue;
    }
    int x = primeFactors(i);
    ans = min(ans, i - x + 1);
  }
  printf("%d\n", ans);
  return 0;
}
