#include <bits/stdc++.h>
using namespace std;
int i, j, k = INT_MIN, p = INT_MAX, n, q, v;
bool prime[1000007];
void era() {
  int i, j;
  memset(prime, 1, sizeof(prime));
  prime[1] = 0;
  prime[0] = 0;
  for (i = 2; i <= n; i++) {
    if (prime[i]) {
      for (j = i + i; j <= n; j += i) {
        prime[j] = 0;
      }
    }
  }
}
int main() {
  cin >> n;
  era();
  for (i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      if (prime[i] == 1) {
        k = max(k, i);
      }
      if (prime[n / i] == 1) {
        k = max(k, n / i);
      }
    }
  }
  for (i = n - k + 1; i <= n; i++) {
    if (prime[i] == 1) continue;
    q = INT_MIN;
    for (j = 1; j * j <= i; j++) {
      if (i % j == 0) {
        if (prime[j] == 1) {
          q = max(q, j);
        }
        if (prime[i / j] == 1) {
          q = max(q, i / j);
        }
      }
    }
    p = min(p, i - q + 1);
  }
  cout << p;
}
