a< =1000,000。
思路：先筛除合数
每读入一个数不是质数的时候一直增加，一直到j是质数
跳过一些已经找到的合数
详见注释
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define NUM 1299709
bool u[NUM+1];
int ans[NUM+1];
void prepare(){//埃筛
for(int i=2;i<=NUM; i++) u[i]=1;//首先认为所有的数都是质数
for(int i=2; i<=NUM; i++){
if(u[i]){
for(int j=i; j<=NUM/i; j++) u[i*j]=0;//筛除合数
}
}
for(int i=2; i<=NUM; i++){
if(!u[i]){//对于合数
int j=i;
while(j<=NUM&&!u[j]) j++;//在j不是质数的时候一直增加，一直到j是质数
j--;//j减1是让j回一个位置，该位置是合数
for(int k=i; k<=j;k++) ans[k]=j-i+1;//从k到j 所有的数字对应的连续合数都是相等的
i=j;//跳过一些已经找到的合数
}else{
ans[i]=0;
}
}
}
int main(){
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
int k;
prepare();
while(scanf("%d",&k)>0&&k>0){
printf("%d\n",ans[k]>0?ans[k]:0);
}
}