#include <bits/stdc++.h>
using namespace std;
int findPrime(int n) {
  for (int i = 2; i < sqrt(n) + 0.1; i++) {
    if (n % i == 0) {
      return findPrime(n / i);
    }
  }
  return n;
}
int main(int argc, char** argv) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int x, y, z, t, r;
  x = 1000000;
  cin >> z;
  t = findPrime(z);
  y = z - t + 1;
  for (int j = y; j < t + y; j++) {
    r = findPrime(j);
    if (r != j) {
      x = min(x, j - r + 1);
    }
  }
  cout << x << endl;
}
