#include <iostream>

using namespace std;

int i_prim(int);

int main()
{
    int n;
    cin>>n;
    cout<<i_prim(n);
    return 0;
}
#include <math.h>

int i_prim(int n){
    int i,j=0,m=n+1,k=n-1;
    while(m){
        for(i=2;i<=sqrt(m);i++){
            if(m%i==0) {
                j=1;
                break;
            }else j=0;
        }
        if(j==0) break;
        m++;
    }
    while(k){
        for(i=2;i<=sqrt(k+1);i++){
            if(k%i==0) {
                j=1;
                break;
            }else j=0;
        }
        if(j==0) break;
        k--;
    }
    n=m-k;
    return n;
}