#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#define maxn 46340  // sqrt(2147483647) < 46341
using namespace std;
bool c[maxn+10];  //0~46340之間false為質數
vector <int> p;    // 2~46340之間的質數共有 4792個
//  p[4791]=46337 , p[4790]=46327，p[4792]=46349

// 以下 isp 為函式， 傳入 n 判斷是否為質數
bool isp(int n)
{
  if(n<=maxn) return( !c[n] );
  int q = (int) sqrt(n);
  int k;
  for(k=0; k<p.size() && p[k]<=q ; ++k)
    if(n%p[k]==0) return false;
  return true;
}
// 篩法建 c[0..46340] 及 vector <int>
void sieve()
{
  int i,j,k;
  memset(c,0,sizeof(c));
  c[0]=c[1]=1;
  for(i=2;i<=maxn;++i)
  {
     if(c[i]==1) continue; //非質數
     p.push_back(i);  // i是質數，放入 p 中
     //是質數的倍數 註記為非質數
     for(j=i+i; j<=maxn; j+=i)
       c[j]=1;
  }
  //  for(k=2; k<=100; ++k)  // 印出 2~100的質數
//    if( !c[k] ) cout << k << endl;
//  cout << p.size() <<" " << p[p.size()-1] << endl;
  return ;
}
// 主程式
int main()
{
  sieve(); //建質數表，有bool c[] 及 vector <int> p
  int n;
  while( cin >> n )
  {
    bool final = isp(n);
    if (final == true) {
        cout << "質數" << endl;
    } else if(final == false) {

        cout << "非質數" << endl;
    }
  }//end while

return 0;

}