Uva 1644 - Prime Gap

// Verdict: Accepted

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<map>
#include<vector>
#include<bitset>

using namespace std;

#define sf scanf
#define pf printf
#define sz 1299711
#define lmt 100005


typedef long long LL;
typedef vector<LL>vll;

LL prm[sz],plen=1;
int ans[sz];

bitset<sz>bs;

void sieve()
{
    LL i , j , pre=2, now=2, anslen=2;

    bs.set();
    bs[0] = bs[1] = 0;

    for(i=2; i<=sz ; i++)
    {
        if(bs[i])
        {
            prm[plen++] = i;

            now = i;

            ans[i] = 0;

            if((now - pre) != 1)
            {
                LL d = now - pre;

                for(LL k=pre+1; k<now; k++)
                {
                    ans[k] = d;
                }
            }

            pre = i;
            now = 0;

            for(j=i*i; j<=sz ; j+=i)
            {
                bs[j] = 0;
            }
        }
    }

    //for(i=1;i<=100;i++)cout<<prm[i] << " ";
    //cout << plen << "\n" << prm[100000];
    //for(i=2; i<=10; i++)cout<< ans[i] << " ";
}

int main()
{
    sieve();

    //freopen("input.txt", "r", stdin);

    int n;

    while(~sf("%d",&n) and n)
    {
        pf("%d\n", ans[n]);
    }

    return 0;
}