3896 소수 사이 수열

https://www.acmicpc.net/problem/3896

에라토스테네스의 체를 이용하여 소수를 구해주자.

#include <cstdio>
 
int t,k,p[1299710];
 
int main()
{
    p[0]=p[1]=true;
    for(int i=2;i*i<1299710;i++) if(!p[i]) for(int j=2*i;j<1299710;j+=i) p[j]=true;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&k);
        if(!p[k])
            printf("0\n");
        else
        {
            int len=1;
            for(int i=k;p[i];i--) len++;
            for(int i=k+1;p[i];i++) len++;
            printf("%d\n",len);
        }
    }
    return 0;
}