#include <bits/stdc++.h>
using namespace std;
long long int n;
long long int x[1000010];
long long int Min = 1e9;
void setup() {
  for (long long int i = (2), __dst = (n); i <= __dst; i++) {
    if (!x[i]) {
      for (long long int j = i * 2; j <= n; j += i) {
        x[j] = i;
      }
    }
  }
}
int main() {
  cin >> n;
  setup();
  for (long long int i = (n - x[n] + 1), __dst = (n); i <= __dst; i++)
    Min = min(Min, i - x[i]);
  cout << Min + 1;
  return 0;
}
