POJ 3518
直接一个素数表二分就可以了
/* POJ 3518 素数表就可以过 */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXM = 1299709 + 10; const int MAXN = 1e5+100; int prime[MAXM]; bool vis[MAXM]; void linear_shaker(){ for(int i = 2;i<MAXM;i++){ if(!prime[i]) { prime[++prime[0]] = i; vis[i] = true; } for(int j = 1;j <= prime[0] && prime[j] <= MAXM / i;j++){ prime[i * prime[j]] = 1; if(i % prime[j] == 0) break; } } } int main(){ linear_shaker(); int n; while(scanf("%d",&n)!=EOF && n){ if(vis[n]) puts("0"); else { int pos = lower_bound(prime+1,prime+1+prime[0],n) - prime; pos -- ; printf("%d\n",prime[pos+1] - prime[pos]); } } return 0; }