#include <bits/stdc++.h>
int lp[1000001];
std::vector<int> prime;
void init() {
  for (int i = 2; i <= 1000000; ++i) {
    if (lp[i] == 0) {
      lp[i] = i;
      prime.push_back(i);
    }
    for (int j = 0;
         j < (int)prime.size() && prime[j] <= lp[i] && i * prime[j] <= 1000000;
         ++j) {
      lp[i * prime[j]] = prime[j];
    }
  }
}
bool is_prime(int number) { return lp[number] == number; }
int gt(int number) {
  while (lp[number] != number) {
    number /= lp[number];
  }
  return number;
}
int min(int a, int b) { return a < b ? a : b; }
int main() {
  init();
  int x2;
  std::cin >> x2;
  int min_x0 = x2;
  for (int x1 = x2 - gt(x2) + 1; x1 <= x2; ++x1) {
    if (!is_prime(x1)) {
      min_x0 = min(min_x0, x1 - gt(x1) + 1);
    }
  }
  std::cout << min_x0 << std::endl;
  return 0;
}
