#include <bits/stdc++.h>
using namespace std;
const int N = 1000000;
int prime[1000001];
void sieve(void) {
  prime[1] = 1;
  int i = 2, j;
  while (i <= N) {
    if (!prime[i]) {
      j = 2 * i;
      while (j <= N) {
        prime[j] = i;
        j += i;
      }
    }
    i++;
  }
  return;
}
int isprime_a(int a) {
  if (a < 2) return 1;
  if (a == 2 || a == 3) return 1;
  if (a % 2 == 0) return 0;
  int root = sqrt(a);
  for (int i = 3; i <= root; i += 2)
    if (a % i == 0) return 0;
  return 1;
}
int min(int a, int b) {
  if (a < b) return a;
  return b;
}
int main() {
  sieve();
  int x2;
  cin >> x2;
  int form = x2 - prime[x2] + 1;
  int to = x2;
  int ans = form;
  for (; form <= to; form++) ans = min(ans, form - prime[form] + 1);
  cout << ans << endl;
  return 0;
}
