UVa 10235 - Simply Emirp

// UVa 10235 - Simply Emirp
#include <iostream>
#include <string>
#include <string.h>
using namespace std;

bool prime[1000000];

long long int reverse(long long int n) {
	long long int m = 0;
	while (n > 0) {
		m = m * 10 + n % 10;
		n /= 10;
	}
	return m;
}

void findprimes() {
	memset(prime, true, sizeof(prime));
	for (int j = 4; j < 1000000; j += 2)
		prime[j] = false;
	for (int i = 3; i < 1000; i++) {
		if (prime[i]) {
			for (int j = i * i; j < 1000000; j += i + i)
				prime[j] = false;
		}
	}
}

int main() {
	findprimes();
	long long int n;
	while (cin >> n) {
		string sol;
		if (!prime[n])
			sol = "is not prime.";
		else if (!prime[reverse(n)] || reverse(n) == n)
			sol = "is prime.";
		else
			sol = "is emirp.";
		cout << n << " " << sol << endl;
	}
	return 0;
}