/* http://projecteuler.net/
 *
 * Problem 49
 * Find arithmetic sequences, made of prime terms, whose four digits are
 * permutations of each other.
 *
 * Solution by Melkor (Filip Niksic, fniksic@gmail.com)
 *
 **/

#include <iostream>
#include <bitset>
#include <cstdlib>

using namespace std;

const int max_num = 10000;

bitset<max_num> sieve;
int digits[10];

void generate_primes() {
    sieve.set();
    sieve.reset(0);
    sieve.reset(1);

    for (int i = 2; i*i < max_num; ++i)
	if (sieve[i])
	    for (int j = i+i; j < max_num; j += i)
		sieve.reset(j);
}

// expects a four-digit number n
bool check_digits(int n) {
    int digits_n[10] = {0};
    while (n > 0) {
	div_t d = div(n, 10);
	++digits_n[d.rem];
	n = d.quot;
	if (digits_n[d.rem] > digits[d.rem])
	    return false;
    }
    return true;
}

void disect(int n) {
    for (int i = 0; i < 10; ++i)
	digits[i] = 0;
    while (n > 0) {
	div_t d = div(n, 10);
	++digits[d.rem];
	n = d.quot;
    }
}

void search() {
    for (int a = 1001; a < 10000; a += 2)
	if (sieve[a]) {
	    disect(a);
	    for (int d = 1; a + 2*d < 10000; ++d)
		if (sieve[a + d] && sieve[a + 2*d]
		    && check_digits(a + d) && check_digits(a + 2*d))
		cout << a << a + d << a + 2*d << endl;
	}
}

int main() {
    generate_primes();
    search();
    return 0;
}