package chelper;

import java.util.ArrayList;
import java.util.List;

import io.InputReader;
import io.OutputWriter;
import misc.SimpleSavingChelperSolution;


public class TaskA extends SimpleSavingChelperSolution {

  public void solve(int testNumber, InputReader in, OutputWriter out) {
    wrapSolve(testNumber, in, out);
  }

  List<Integer> primes(int n) {
    boolean[] a = new boolean[n];

    List<Integer> res = new ArrayList<>();

    for (int i = 2; i < n; i++) {
      if (a[i]) {
        continue;
      }

      res.add(i);

      for (int j = i; j < n; j += i) {
        a[j] = true;
      }
    }

    return res;
  }

  @Override
  public void solve(int testNumber) {
    int N = 1100000;

    List<Integer> primes = primes(N);

    int x2 = in.nextInt();

    int r = x2 + 1;
    int l = x2;

    for (Integer prime : primes) {
      if (x2 % prime == 0) {
        l = x2 - prime + 1;
      }
    }

    int minX0 = x2;

    for (Integer prime : primes) {
      int minX1 = (l + prime - 1) / prime * prime;

      if (minX1 >= r) {
        continue;
      }

      int next = minX1 - prime + 1;
      if (minX1 == prime) {
        next = prime;
      }

      minX0 = Math.min(minX0, next);
    }

    out.println(minX0);

  }
}