#include <bits/stdc++.h>
using namespace std;
int main() {
  int t = 1;
  for (int tt = 1; tt <= t; tt++) {
    int p[] = {2,   3,   5,   7,   11,  13,  17,  19,  23,  29,  31,  37,  41,
               43,  47,  53,  59,  61,  67,  71,  73,  79,  83,  89,  97,  101,
               103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
               173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239,
               241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
               317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
               401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467,
               479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569,
               571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643,
               647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
               739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823,
               827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
               919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997};
    int m = 2000000000, n, i, j, k = 0, l = 1, count = 168, nn;
    cin >> n;
    nn = n;
    for (i = 0; i < count && p[i] < n; i++) {
      while (n % p[i] == 0) {
        l = p[i];
        n = n / l;
      }
    }
    if (n > l) l = n;
    l = nn - l;
    for (n = nn; n > l; n--) {
      k = 0;
      i = n;
      for (j = 0; j < count && p[j] < i; j++) {
        while (i % p[j] == 0) {
          k = p[j];
          i /= k;
        }
      }
      if (i > k && k != 0) k = i;
      if (m > n - k + 1 && k != 0) {
        m = n - k + 1;
      }
    }
    cout << m << endl;
  }
}
