#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e6;

int i,j,k,tmp,x,l,ans;

bool mark[MAXN+];

vector<int> Prime;

template <typename T> inline void read(T &x) {

        int f = ; x = ;

        char c = getchar();

        for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }

        for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

        x *= f;

}

template <typename T> inline void write(T x) {

        if (x < ) { putchar('-'); x = -x; }

        if (x > ) write(x/);

        putchar(x%+'');

}

template <typename T> inline void writeln(T x) {

        write(x);

        puts("");

}

int main() {

        read(x);

        for (i = ; i <= MAXN; i++) {

                if (!mark[i]) Prime.push_back(i);

                for (k = ; k < Prime.size(); k++) {

                        tmp = i * Prime[k];

                        if (tmp > MAXN) break;

                        mark[tmp] = ;

                        if (i % Prime[k] == ) break;

                }

        }

        for (i = ; i < Prime.size(); i++)

                if (x % Prime[i] == ) l = x - Prime[i] + ;

        ans = x;

        for (i = ; i < Prime.size(); i++) {

                for (j =  * Prime[i]; j <= x; j += Prime[i]) {

                        if (j < l) continue;

                        ans = min(ans,j-Prime[i]+);

                }

        }

        writeln(ans);

        return ;

}