Untitled

#include<stdio.h>
#include<cmath>
#include<string.h>
#include<vector>
using namespace std;

const int sqrtMax = 65537;

bool primeTable[sqrtMax+1];
vector<int > prime;

void init(){
	memset(primeTable,true,sizeof(primeTable));
	primeTable[0]=false;
	primeTable[1]=false;
	for(int i=2; i<=sqrtMax; i++){
		if(primeTable[i] == true){
			prime.push_back(i);
			for(int j=i*2; j<=sqrtMax; j+=i){
				primeTable[j] = false;
			}
		}
	}
	return;
}

bool isPrime(int num){
	if(num <= sqrtMax){
		return primeTable[num];
	}
	else{
		int sqrtNum=sqrt(num);
		for(int i=0; i<prime.size() && prime[i]<=sqrtNum ; i++){
			if(num%prime[i]==0){
				return false;
			}
		}
		return true;
	}
}

int main(){
	init();
	int n;
	while(scanf("%d",&n)!=EOF){
		if(isPrime(n)){
			printf("質數\n");
		}
		else{
			printf("非質數\n");
		}
	}
}