#include <bits/stdc++.h>
using namespace std;
char g[777][777];
long long n, sn[100007], p[1000007], tot, cur, ans;
void omar() {
  for (int i = 2; i <= 1000000; i++) {
    if (p[i]) {
      continue;
    }
    for (int j = i; j <= 1000000; j += i) {
      p[j] = i;
    }
  }
}
int main() {
  omar();
  scanf("%lld", &n);
  ans = n - 1;
  for (int i = n - p[n] + 1; i < n; i++) {
    if (p[i] == i) continue;
    ans = min(ans, i - p[i] + 1);
  }
  printf("%lld", ans);
}
