【题解】UVa 1644【Prime Gap】

分析

这种水题，把素数筛出来，暴力枚就好了。

代码

#include<cstdio>
#include<algorithm>
using std::fill;
const int MAXN = 2000000 + 6;
int primes[MAXN],num;
bool isPrime[MAXN];

void sieve(){
    fill(isPrime,isPrime + MAXN,true);
    num = 0;
    for(int i = 2;i < MAXN;++i){
        if(isPrime[i]) primes[num++] = i;
        static int d;
        for(int j = 0;j < num && (d = i * primes[j]) < MAXN;++j){
            isPrime[d] = false;
            if(i % primes[j] == 0) break;
        }
    }
}

int main(){
    sieve();
    int n;
    while(scanf("%d",&n) == 1 && n){
        if(isPrime[n]){printf("0\n");continue;}
        for(int i = 0;i < 100000;i++){
            if(primes[i] > n){printf("%d\n",primes[i] - primes[i - 1]);break;}
        }
    }

    return 0;
}