素数环 -- C++实现

浏览数：20 / 时间：2015年06月08日

问题描述：将从1到n这n个整数围成一个圆环，若其中任意2个相邻的数字相加，
结果均为素数，那么这个环就成为素数环。

n=20时，下面的序列就是一个素数环：

1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 20 11 12 19 18

英文名：Prime Ring Problem

解题分析：
对于这样的问题，我的想法就是首先要判断每个数是否是素数，
接着继续判断如何是否相邻的两个数的和是素数。

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#define MAXN 20
using namespace std;
int ring[MAXN], b[MAXN];

int isPrime(int n)
{
   int t, f = 1;
   t = sqrt(n);
   for(int i = 2; i <= t; i++)
   if(n % i == 0)
   {
       f = 0;
       break;
   }
   return f;
}

int primeRing(int ring[], int b[], int n)
{
   if(n == MAXN)
       return isPrime(ring[n - 1] + ring[0]);
   printf("\nCalculating ring[%d] = ", n);
   for(int i = 1; i < MAXN; i++)
   {
       if( b[i] == 0 && isPrime((i + 1) + ring[n - 1]))
       {
           b[i] = 1;
           ring[n] = i + 1;
           printf("%d ", ring[n]);
           if( primeRing(ring, b, n + 1) )
               return 1;
           else
               b[i] = 0;
       }
   }
   return 0;
}
int main()
{
   ring[0] = 1;
   b[0] = 1;
   if( primeRing(ring, b, 1) )
   {
       printf("\n\nThe prime ring is : ");
       for(int i = 0; i < MAXN; i++)
       printf("%d", ring[i]);
       printf("\n");
   }
   else
       printf("\n\nNot found!\n");
   return 0;
}