#include <bits/stdc++.h>
using namespace std;
int prime[1000005];
void seive() {
  int i, j;
  for (i = 2; i <= 1000000; ++i) {
    if (!prime[i]) {
      for (j = i * 2; j <= 1000000; j += i) prime[j] = max(prime[j], i);
    }
  }
}
int main() {
  seive();
  int i, j, x2, ans = 2000000;
  scanf("%d", &x2);
  int s = sqrt(x2);
  int temp = x2;
  for (i = 2; i <= s; ++i) {
    if (temp % i == 0) {
      for (j = x2; j > x2 - i; --j) {
        ans = min(ans, j - prime[j] + 1);
      }
    }
    while (temp % i == 0) temp /= i;
  }
  if (temp > 1) {
    for (j = x2; j > x2 - temp; --j) {
      ans = min(ans, j - prime[j] + 1);
    }
  }
  printf("%d\n", ans);
  return 0;
}
