#include <stdio.h>
#include <string.h>
#include <math.h>

int main(){
  int a[4793];
 int b;
 int t;
 int e;
 int x;
 int ct;
 b = 2;
 e = 1;

 a[1] = 2;
 while (b != 46340)
 {
  b++;

  x = 0;
  t = 0;
  while (t<e && x == 0)
  {
   t++;
   if (b % a[t] == 0)
   {
    x = 1;
   }
  }
  if (x == 0)
  {
   e++;
   a[e] = b;
 
  }
 }
 while (scanf("%d", &ct) != EOF)
 {
  b = 1;
  x = 0;
  while (b!= e && x == 0)
  {
  
   if (ct == a[b])
   {
    x = 1;
   }
   b++;
  }
  if (x == 1)
  {
   printf("質數\n");
  }
  else
  {
   printf("非質數\n");
  }

 }
 return(0);

}

求解