学步园

#include<cstdio>
#include<cstring>
using namespace std;

const int MAX = 1299710;
int p[MAX], a[MAX], pn;;

void prime ()
{
    int i, j; pn = 0;
    memset(a,0,sizeof(a));
    for ( i = 2; i < MAX; i++ )
    {
        if ( ! a[i] ) p[pn++] = i;
        for ( j = 0; j < pn && i*p[j] < MAX && ( p[j] <= a[i] || a[i] == 0 ); j++ )
            a[i*p[j]] = p[j];
    }
}

int main()
{
    prime();
    int num, i;
    while ( scanf("%d",&num) && num )
    {
        if ( ! a[num] ) { printf("0\n"); continue; }
        for ( i = 1; i < pn; i++ )
            if ( p[i-1] < num && p[i] > num )
                break;
        printf("%d\n",p[i]-p[i-1]);
    }
    return 0;
}