#include <bits/stdc++.h>
using namespace std;
bool isprime(int x) {
  for (int i = 2; i * i <= x; i++)
    if (!(x % i)) return false;
  return true;
}
int main() {
  int x2, min1 = 1000000;
  cin >> x2;
  int n = x2;
  vector<char> prime(n + 1, true);
  prime[0] = prime[1] = false;
  for (int i = 2; i <= n; ++i)
    if (prime[i])
      if (i * 1ll * i <= n)
        for (int j = i * i; j <= n; j += i) prime[j] = false;
  for (int i = 1; i * i <= x2; i++) {
    if (!(x2 % i)) {
      if (isprime(i)) {
        for (int z = x2 - i + 1; z < x2; z++) {
          if (prime[z]) min1 = min(min1, z);
          for (int k = 2; k * k <= z; k++) {
            if (!(z % k)) {
              if (prime[k]) min1 = min(min1, z - k + 1);
              if (prime[z / k]) min1 = min(min1, z - z / k + 1);
            }
          }
        }
      }
      if (prime[x2 / i]) {
        for (int z = x2 - x2 / i + 1; z < x2; z++) {
          if (prime[z]) min1 = min(min1, z);
          min1 = min(min1, z);
          for (int k = 2; k * k <= z; k++) {
            if (!(z % k)) {
              if (prime[k]) min1 = min(min1, z - k + 1);
              if (prime[z / k]) min1 = min(min1, z - z / k + 1);
            }
          }
        }
      }
    }
  }
  cout << min1;
}
