p60.cpp

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<long long> *primeTable;

long long nextPrime()
{
    long long lastPrime = *--(primeTable->end());
    do
    {
        lastPrime += 2;
        long long divisionLimit = (long long) sqrt((double)lastPrime);
        for (auto divisor : *primeTable)
        {
            if (divisor > divisionLimit) return lastPrime;
            if (!(lastPrime % divisor))
            {
                break;
            }
        }
    }
    while (true);
}

bool isPrime(long long numberToTest)
{
    long long knownMaxPrime = *--(primeTable->end());
    if (numberToTest == knownMaxPrime)
    {
        return true;
    }
    if (numberToTest < knownMaxPrime)
    {
        int leftIndex = 0, rightIndex = primeTable->size();
        while(leftIndex < rightIndex)
        {
            int middleIndex = (rightIndex+leftIndex)/2;
            long long middleNum = (*primeTable)[middleIndex];
            if (numberToTest == middleNum) return true;
            if (numberToTest > middleNum) leftIndex = middleIndex + 1;
            else rightIndex = middleIndex;
        }
        return false;
    }
    while (true)
    {
        knownMaxPrime = nextPrime();
        primeTable->push_back(knownMaxPrime);
        if (knownMaxPrime == numberToTest)
        {
            return true;
        }
        if (knownMaxPrime > numberToTest)
        {
            return false;
        }
    }
    // you can't excuete to here
    throw 233;
    return false;
}

long long combine(long long left, long long right)
{
    long long _left = left;
    long long _right = right;
    do
    {
        _left *= 10;
    }
    while (_right /= 10);
    return _left + right;
}

bool isGood(long long testNum, vector<long long>& numSet)
{
    for (auto num : numSet)
    {
        if (!isPrime(combine(testNum, num)) || !isPrime(combine(num, testNum)))
        {
            return false;
        }
    }
    return true;
}

struct numberGroupNode
{
    vector<long long> numbers;
    numberGroupNode *next;
};

void deleteChain(numberGroupNode *node)
{
    if (!node) return;

    numberGroupNode *currentNode = node;
    numberGroupNode *nextNode;
    do
    {
        nextNode = currentNode->next;
        delete node;
        currentNode = nextNode;
    }
    while (currentNode);
}

long long solve(int n)
{
    if (1==n) return 3;

    numberGroupNode** numberGroups = new numberGroupNode*[n];
    for (int i=0; i<n; ++i)
    {
        numberGroups[i] = new numberGroupNode();
    }
    numberGroupNode *initialNode = new numberGroupNode();
    initialNode->numbers.push_back(3);
    numberGroups[0]->next = initialNode;

    bool solved = false;
    long long result = 0;
    int currentIndex = 1;
    while (true)
    {
        long long newPrime = (*primeTable)[currentIndex];

        numberGroupNode *visitNode;
        numberGroupNode *newNode;

        for (int i=0; i<n; ++i)
        {
            visitNode = numberGroups[i];
            while (visitNode->next)
            {
                visitNode = visitNode->next;
                if (isGood(newPrime, visitNode->numbers))
                {
                    if (i == n-2)
                    {
                        solved = true;
                        long long sum = newPrime;
                        for (auto num : visitNode->numbers) sum += num;
                        result = sum;

                        for (auto num: visitNode->numbers) cout << num << " ";
                        cout << newPrime << endl;
                        break;
                    }
                    newNode = new numberGroupNode();
                    newNode->numbers = visitNode->numbers;
                    newNode->numbers.push_back(newPrime);
                    numberGroupNode *nextLevelVisitNode = numberGroups[i+1];
                    while(nextLevelVisitNode->next) nextLevelVisitNode = nextLevelVisitNode->next;
                    nextLevelVisitNode->next = newNode;
                }
            }
            if (solved)
            {
                break;
            }
        }

        if (solved)
        {
            break;
        }

        newNode = new numberGroupNode();
        newNode->numbers.push_back(newPrime);
        visitNode = numberGroups[0];
        while (visitNode->next) visitNode = visitNode->next;
        visitNode->next = newNode;
        ++currentIndex;
    }

    for (int i=0; i<n; ++i) deleteChain(numberGroups[i]);
    delete[] numberGroups;
    return result;
}

int main()
{
    primeTable = new vector<long long>();
    primeTable->push_back(3);
    isPrime(1000);

    cout << solve(5) << endl;

    delete primeTable;
    return 0;
}