#include <bits/stdc++.h>
using namespace std;
long long a[1000005] = {1, 1}, b[1000005], num;
long long x2, ans = 100000000;
void init() {
  long long i, j;
  for (i = 2; i <= 1000000; i++) {
    if (a[i]) continue;
    for (j = i * i; j <= 1000000; j += i) a[j] = 1;
  }
  for (i = 1; i <= 1000000; i++)
    if (a[i] == 0) b[++num] = i;
}
int main(void) {
  init();
  scanf("%lld", &x2);
  long long x = x2, p = 0;
  for (long long i = 1; b[i] * b[i] <= x; i++)
    while (x % b[i] == 0) x /= b[i], p = b[i];
  if (x != 1) p = x;
  for (long long i = x2 - p + 1; i <= x2; i++) {
    long long tmp = i;
    long long pp = p;
    for (long long j = 1; b[j] * b[j] <= tmp; j++)
      while (tmp % b[j] == 0) tmp /= b[j], pp = b[j];
    if (tmp != 1) pp = tmp;
    if (pp == i) continue;
    ans = min(ans, i - pp + 1);
  }
  printf("%lld\n", ans);
  return 0;
}
