/* http://projecteuler.net/
 *
 * Problem 41
 * What is the largest n-digit pandigital (uses all the digits 1 to n
 * exactly once) prime that exists?
 *
 * Solution by Melkor (Filip Niksic, fniksic@gmail.com)
 *
 **/

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

using namespace std;

const int prime_limit = 7654322;

bitset<prime_limit> sieve;

bitset<10> digits;
int candidate = 0;

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

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

inline bool is_prime(int n) {
    return sieve[n];
}

// 8 and 9-digit pandigital numbers are divisible by 3 so they
// cannot be prime. Function check expects n<=7
void check(int depth, int n) {
    if (depth >= n) {
	if (is_prime(candidate)) {
	    cout << candidate << endl;
	    exit(0);
	}
	return;
    }

    for (int i = n; i >= 1; --i)
	if (!digits[i]) {
	    digits.set(i);
	    candidate = candidate * 10 + i;
	    check(depth + 1, n);
	    candidate /= 10;
	    digits.reset(i);
	}
}

int main() {
    generate_primes();
    // couple of tests
    cout << is_prime(7654321) << endl;
    cout << is_prime(2) << endl;
    cout << is_prime(65535) << endl;

    for (int n = 7; n > 0; --n)
	check(0, n);
    return 0;
}