#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
const int N = 1000100;
int prime[N];
void Prime() {
  int n = 2;
  while (n < N) {
    int num = n * 2;
    while (num < N) {
      prime[num] = n;
      num += n;
    }
    num = n + 1;
    while (prime[num] && num < N) {
      num++;
    }
    n = num;
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  Prime();
  int x0, x1, x2;
  cin >> x2;
  int a, b;
  x0 = N * 100;
  b = prime[x2];
  for (int i = x2 - b + 1; i <= x2; i++) {
    a = prime[i];
    x0 = min(x0, i - a + 1);
  }
  cout << x0 << '\n';
  return 0;
}
