prime_sieve(code)............

#include<iostream>
#include<cmath>
#include<cstdlib>
using namespace std;
bool a[1000001];
void sieve()
{
    long long i,j,m;
    m=sqrt(1000000);
    a[1]=1;
    a[0]=1;
    for(i=3;i<=m;i+=2)
    {
        if(a[i]==0)
        for(j=i*i;j<=1000000;j+=i+i)
        a[j]=1;
    }
}
int main()
{
    sieve();
    long long m;
    while(cin>>m)
    {
        if(m!=2&&m%2==0)
        cout<<"not prime"<<endl;
        else if(a[m]==0)
        cout<<"prime"<<endl;
        else
        cout<<"not prime"<<endl;
    }
}