Prime Gap

It's written in Chinese.

Descriptions:

For a number n, if n is a prime number, then output 0; otherwise, find the two prime numbers with the minimum distance n, one greater than N and one less than N, and output their difference (positive number).

Input

Multi group input

Each line contains a number n

If n is 0, the program ends

Output

For each test data, output one answer in one line

Sample Input

Sample Output

Title Link:

https://vjudge.net/problem/UVA-1644

For water problem, first find the prime table, process the prime number in advance, then input n, if n is the prime number, output 0, if not, scan back from the second prime number, when the first number greater than n appears, you can subtract the previous prime number, that is the answer.

AC code

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define ME0(x) memset(x,0,sizeof(x))
using namespace std;
int T;
int n;
int isprime[1300005];//Determine which number is prime in this
int ans[1300005];//Save all prime numbers into an array for easy searching
void eratos(int x)//Prime number table
{
    for(int i=0; i<=x; ++i)
        isprime[i]=true;
    isprime[0]=isprime[1]=false;
    for(int i=2; i<=x; ++i)
    {
        if(isprime[i])
        {
            int j=i+i;
            while(j<=x)
            {
                isprime[j]=false;
                j+=i;
            }
        }
    }
}
void solve()
{
    if(isprime[n])
    {
        cout<<0<<endl;
        return;
    }
    else
    {
        for(int i=1; ;++i)
        {
            if(ans[i]<n&&ans[i+1]>n)
                {
                    cout<<ans[i+1]-ans[i]<<endl;
                    return;
                }
        }

    }
}
int main()
{
    int j=-1;
    eratos(1300005);
    for(int i=2; i<=1300005; ++i)
        if(isprime[i])
            ans[++j]=i;
//    for(int i=0; i<=10; ++i)
//        cout<<ans[i]<<endl;
    while(cin>>n,n)
    {
        solve();
    }
}