# UVa 524 - Prime Ring

## The challenge

A ring is composed of n (even number) circles as shown in diagram. Put natural numbers 1,2,...,n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

### Input

$n\quad (0 \lt n \le 16)$

### Output

The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. You are to write a program that completes above process.

### Sample Input

6
8


### Sample Output

Case 1:

1  4  3  2  5  6
1  6  5  2  3  4


Case 2:

1  2  3  8  5  6  7  4
1  2  5  8  3  4  7  6
1  4  7  6  5  8  3  2
1  6  7  4  3  8  5  2


## My solution

#include <iostream>
#include <algorithm>

const int MAX_P = 50;
bool primes[MAX_P];

void gen_primes()
{
std::fill(primes, primes + MAX_P, true);

primes[0] = primes[1] = false;

for ( int i = 4; i < MAX_P; i += 2 )
{
primes[i] = false;
}

// discard other prime numbers(3, 5, ..)'s multiples
for ( int p = 3; p < MAX_P; p += 2 )
{
if ( !primes[p] )
continue;

for ( int i = p * p; i < MAX_P; i += 2 * p )
{
primes[i] = false;
}
}
}

const int MAX = 17;
int prime_ring_idx, n;
int prime_ring[MAX];
bool number_taken[MAX];

void print_prime_ring()
{
std::cout << 1;
for ( int i = 2; i <= n; ++i )
{
std::cout << " " << prime_ring[i];
}
std::cout << std::endl;
}

void gen_prime_ring()
{
// all n numbers filled, print the solution
if ( prime_ring_idx >= n )
{
print_prime_ring();
return;
}

for ( int i = 2; i <= n; ++i )
{
if ( !number_taken[i] &&
primes[i + prime_ring[prime_ring_idx]] )
{
// if it is nth number check if it can make a prime
// with the first number, so as to complete the circle
if ( prime_ring_idx == n - 1 &&
!primes[i + prime_ring[1]] )
{
continue;
}

number_taken[i] = true;
prime_ring[++prime_ring_idx] = i;

gen_prime_ring();

number_taken[i] = false;
prime_ring[prime_ring_idx--] = 0;
}
}
}

int main()
{
int c = 1;

gen_primes();
prime_ring[1] = 1;

// initially no numbers are taken
for ( int i = 0; i < MAX; ++i )
{
number_taken[i] = false;
}

// 1 will always be the first number for the circle so take it
number_taken[1] = true;

while ( std::cin >> n )
{
if ( c != 1 )
{
std::cout << std::endl;
}
std::cout << "Case " << c++ << ":" << std::endl;

prime_ring_idx = 1;
gen_prime_ring();
}
return 0;
}


Share your ideas to improve my code on:

• Efficiency
• Code style
• Design patterns