d709: 判断质数（一）. FYI: https://yunlinsong.blogspot.com/2015/03/d709.html

d709.cpp

#include <stdio.h>
#include <cmath>

using namespace std;

const int limitValue = 1000000;

//const int num = 78498;
const int num = 78500;

bool primeFlag[limitValue + 1];

int prime[num+1];
int cnt = 0;

void genPrimeArray()
{
	prime[0] = 2;
	prime[1] = 3;
	prime[2] = 5;
	prime[3] = 7;
	prime[4] = 11;
	prime[5] = 13;
	
	primeFlag[2] = 1;
	primeFlag[3] = 1;
	primeFlag[5] = 1;
	primeFlag[7] = 1;
	primeFlag[11] = 1;
	primeFlag[13] = 1;
	
	int index = 6;
	
	bool isPrime;
	for(int i = 15; i <= limitValue; i += 2)
	{
		isPrime = true;
		int k = 1;
		int terminal = sqrt(i);
		for(int c = prime[k]; c <= terminal; k++, c = prime[k])
		{
			if( i % c == 0)
			{
				isPrime = false;
				break;
			}
		}
		
		if(isPrime == true)
		{
			prime[index] = i;
			primeFlag[prime[index]] = 1;
			index++;
		}
	}
}

int main(void) {	
	genPrimeArray();
	
	int p ;
	while(scanf("%d",&p)&& p!=0){
		printf("%d\n", 1 - primeFlag[p]) ;
	}
	

	return 0;
}