Necklace counting problem-with consecutive prime constraint

This is codeEval challenge to count the number of chains possible to make with beads holding numbers. Constraint is sum of the consecutive beads of chain should be a prime number.

The standard algorithm std::next_permutation is very resource oriented in this case, so dropped the idea to use that one.

I created a simple algorithm. If the input number is 4, we have to consider numbers 1-4. If we take permutations of 2-4 and append 1 to all resultant permutations we will get all possible necklaces without repetition using numbers 1-4. The above stated is the basic approach.

By considering, beads should be placed in chain to satisfy the prime number constraints at least, they should be in even number after odd number order or vice versa. Since I am always starting with 1, I have chosen the odd number before even number order.

My solution is not yet accepted because of performance constraints in that it should output answers for 5 input even numbers within 10 seconds. On my Intel dual core system by using O3 compiler optimization, it is taking 35 seconds and without optimization in range of 180-200 seconds for the number 18. For all other numbers up to 16 it will execute before 10 seconds.

I created an array of possible eligible digits to get position in the chain.

int prime_vec[10][8]={ {},
                           { 2, 4, 6, 10, 12, 16, 18, 0 },     //1//
                           { 2, 4, 8, 10, 14, 16, 0, 0  },        //3//
                           { 2, 6, 8, 12, 14, 18, 0, 0  },       //5//
                           { 4, 6, 10, 12, 16, 0, 0, 0  },         //7
                           { 2, 4, 8, 10,  14, 0, 0, 0  },          //9
                           { 2, 6, 8, 12,  18, 0, 0, 0 },          //11
                           { 4, 6, 10, 16, 18, 0, 0, 0 },         //13
                           { 2, 4, 8, 14,  16, 0, 0, 0 },          //15
                           { 2, 6, 12, 14,  0, 0, 0, 0 } };          //17

If the last digit in so far

You can improve the performance by using a more efficient algorithm.

Instead of generating all possible combinations, one can count them using dynamic programming.

The state is (mask, last_number), where mask indicates which numbers were already used. A transition is adding a number cur such that it is not in the mask and last_number + cur is a prime. The answer is sum of f(2^n - 1, x) such that x + 1 is prime. Here is a pseudo code of this solution:

def solve(n)
    isPrime = new Array[n + 1, n + 1]
    for i = 1 .. n
        for j = 1 .. n
            isPrime[i][j] = checkIfPrime(i + j) // checks if a number is prime somehow(for instance, by trial division)
    dp = new Array(2^n, n + 1)
    dp(1, 1) = 1 // There is one way to put number one.
    for mask = 0 .. (2^n - 1)
        for last = 1 .. n
            for cur = 1 .. n
                if isPrime[last][cur] && last in mask && not cur in mask
                     dp[mask with cur][cur] += dp[mask][last]
    return sum dp[2^n - 1][x] for all x such that 1 + x is prime

We can check that a number is in a mask using bitwise operations(and we add a new number to a mask in the same way), so the total time complexity is O(2^n * n^2).

It is also possible to improve the constant factor by checking only even cur when last is odd (and vice versa) or by precomputing the list of all cur such that cur + last is a prime before running the dynamic programming.

StackExchange Code Review Q#88641, answer score: 2