因为测试点是1-1000000，埃氏筛过不了，只能用线性筛。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int p[100005],t;
bool q[1000005];
void P(int u)//线性筛
{
    q[0]=q[1]=1;
    for(int i=1;i<=u;i++)
    {
        if(!q[i])p[++t]=i;
        for(int j=1;j<=t&&i*p[j]<=u;j++)
        {
            q[i*p[j]]=1;
            if(!(i%p[j]))break;
        }
    }
}
int K(int u)//翻转
{
    int x=u,s=0;
    while(x)s*=10,s+=x%10,x/=10;
    return s;
}
int main()
{
    int n;
    P(1000000);
    while(scanf("%d",&n)!=EOF)
    {
        if(q[n])printf("%d is not prime.",n);
        else if(!q[K(n)]&&n!=K(n))printf("%d is emirp.",n);//注意不是回文数
        else printf("%d is prime.",n);
        puts("");
    }
    return 0;
}