1. C++, Tobias Fuchs


/* Problem: 10235
* Author: Tobias Fuchs
* Verdict: Accepted
* Runtime: 0.140
*/

#include<iostream>
#include<string>
#include<vector>
#include<string.h>
#include<cstdlib>

#define log(m) ::std::cout << "log: '" << m << "'" << ::std::endl

using ::std::cin;
using ::std::string;

/* max input value is 1.000.000 = 1000 * 1000
*/
#define MAX_PRIME_SQRT 1000
#define MAX_PRIME (MAX_PRIME_SQRT*MAX_PRIME_SQRT)

/* We want linearized access to this map, so
* do not use ::std::vector, but a simple
* 2-dim array of integers.
*/
bool primes[MAX_PRIME_SQRT][MAX_PRIME_SQRT];

/* Provides serialized accesso to map of primes.
* Map is generated using Sieve of Eratosthenes.
*/
inline bool
is_prime(unsigned int n)
{
return (*primes)[n];
}

/* Building map of primes.
* Implements Sieve of Erastothenes.
*/
void
build_primes()
{
unsigned int step = 2;
unsigned int mark = 1;
memset(primes, true, MAX_PRIME);
while(step < MAX_PRIME_SQRT) {
mark = step;
while(mark+step < MAX_PRIME) {
mark += step;
(*primes)[mark] = false;
}
do { ++step; } while(!is_prime(step));
}
(*primes)[0] = false;
(*primes)[1] = false;
}
void
set_to_next_prime(unsigned int * value_ref) {
do { ++(*value_ref); } while(!is_prime((*value_ref)));
}
void
set_to_prev_prime(unsigned int * value_ref) {
do { --(*value_ref); } while(!is_prime((*value_ref)));
}

unsigned int reverse_uint(unsigned int value)
{
unsigned int rev;
rev = 0;
while(value > 0)
{
rev = (rev * 10) + value % 10;
value /= 10;
}
return rev;
}

int
main()
{
string nr_str;
unsigned int nr, nr_rev;

build_primes();

::std::vector<unsigned int> twins;

while(cin >> nr_str)
{
nr = atoi(nr_str.c_str());
nr_rev = reverse_uint(nr);
::std::cout << nr;
if(is_prime(nr)) {
if(is_prime(nr_rev) && nr != nr_rev) {
::std::cout << " is emirp." << ::std::endl;
}
else {
::std::cout << " is prime." << ::std::endl;
}
}
else {
::std::cout << " is not prime." << ::std::endl;
}
}
return 0;
}