1
\$\begingroup\$

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;

  // discard 2's multiples
  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
  • Readability
\$\endgroup\$
  • \$\begingroup\$ This problem seems really poorly specified. Is the idea that you can't repeat any number in the ring? That appears to be the case from the sample output, but I don't see that specified anywhere. If not, couldn't you simply always fill it with 1s? \$\endgroup\$ – user1118321 Jan 1 '17 at 16:56
  • \$\begingroup\$ yeah, you can't repeat any number in the ring \$\endgroup\$ – Abhisek Jan 2 '17 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.