C# 素数环

Virgo-Star

求用C#解决素数环问题的代码啊，谢谢

站长苏飞

给出一个N(0<N<20)，在1~N的所有排列中，满足相邻两个数之和是素数（头尾相邻）的排列输出

比如当N = 4时，满足条件的素数环有如下几种

1 2 3 4
1 4 3 2
2 1 4 3
2 3 4 1
3 2 1 4
3 4 1 2
4 1 2 3
4 3 2 1

常规的做法是，找出这N个数的所有排列，然后依次检查每个排列，筛选出符合条件的排列即可。求排列可以用回溯法的排列树模型，筛选就按照题目要求即可，判断素数的算法也有很多，选择一个即可。注意不要忘记最后一个元素和第一个元素的检测。优化前的代码如下:

[C#] 纯文本查看 复制代码

代码

Code highlighting produced by Actipro CodeHighlighter (freeware)[url=http://www.CodeHighlighter.com/-->]http://www.CodeHighlighter.com/-->[/url] 1 // Is n prime ?
bool IsPrime(int n)
{
    for (int i = 2; i * i <= n; i++)
        if(n % i == 0)
            return false ;
    return true ;
}

// Check a permutation
bool Check(int a[], int n)
{
    if(!IsPrime(a[0] + a[n - 1]))
        return false ;

    for(int i = 0; i < n - 1; i++) // avoid duplicate
        if(!IsPrime(a + a[i + 1]))
            return false ;

    return true ;
}

void Perm(int a[], int n, int t)
{
    if(t == n)
    {
        if(Check(a, n))
            Output(a, n) ;
    }
    else
    {
        for(int k = t; k < n; k++)
        {
            swap(a[k], a[t]) ;
            Perm(a, n, t + 1) ;
            swap(a[k], a[t]) ;
        }
    }
}

题目不难，做完以后，我发现有很多可以优化的地方，可以大幅提高速度。

1. 首先，找出所有排列并逐个检查，这是很浪费时间的，更高效的方法是，一边排列一边检查，这样可以提早发现不满足条件的候选解，提早剪枝，避免不必要的搜索，例如当N=10时，排列到1234的时候，满足条件，下一次选择5，序列变为12345，由于4 + 5 = 9，非素数，所以后面不用再排列了，也就是从当前位置开始，以5为根的子树可以不用再搜索了，直接跳到6，序列变为12346，由于4 + 6 = 10，非素数，同样舍弃6为根的子树。下一次搜索变成12347，这回满足条件，继续排列下一个元素，如此直到10个元素全部排列完成。代码如下：a是储存排列的数组，n是元素个数，t用来控制递归过程。

[C#] 纯文本查看 复制代码

Code highlighting produced by Actipro CodeHighlighter (freeware)[url=http://www.CodeHighlighter.com/-->]http://www.CodeHighlighter.com/-->[/url] 1 void PrimeCircle(int a[], int n, int t)
{
    if(t == n)
    {
        Output(a, n) ; // 找到一个解
    }
    else
    {
        for(int i = 1; i <= n; i++)
        {
            a[t] = i ;
            if(IsOk(a)) // 检查当前值，满足条件才继续
                PrimeCircle(a, n, t + 1) ;
        }
    }
}

2. 再看题目的输入范围，1 < N < 20，由于输入规模比较小，所以考虑使用查表法来判定素数，查表法是典型的以空间换时间的方法。20以内两个数之和最大是18 + 19 = 37，而37以内的素数分别是2， 3， 5， 7， 11， 13， 17， 19， 23， 29， 31， 37，我们可以定义一个38个元素的数组，当i为素数时，令a = 1，否则a = 0。这样，要判断一个数是否为素数时，直接判断a是否为1即可。对应的数组如下：

[C#] 纯文本查看 复制代码

Code highlighting produced by Actipro CodeHighlighter (freeware)[url=http://www.CodeHighlighter.com/-->]http://www.CodeHighlighter.com/-->[/url] 1 int prime[38] = 
{
    0, 0, 1, 1, 0, 1, 0, 
    1, 0, 0, 0, 1, 0, 1, 
    0, 0, 0, 1, 0, 1, 0, 
    0, 0, 1, 0, 0, 0, 0, 
    0, 1, 0, 1, 0, 0, 0,
    0, 0, 1,
} ;

判断i是否为素数的代码也很简单

[C#] 纯文本查看 复制代码

if (prime == 1)  //素数
 {
 // do something
 }

3. 再考虑输入的特点，如果输入N是奇数的话，由于起点从1开始，那么1-N之间一共有N / 2个偶数，N / 2 + 1个奇数，也就是奇数的个数比偶数多一个，那么把这N个数排成一个环，根据鸽巢原理，必然有两个奇数是相邻的，而两个奇数之和是偶数，偶数不是素数，所以我们得出结论，如果输入N是奇数的话，没有满足条件的排列。这样当N是奇数的时候，直接返回即可。如果1-N之间每个数输入的几率相同，这个判断可以减少一半的计算量。

[C#] 纯文本查看 复制代码

1 if(n & 1) // 奇数无解，直接返回
2     return ;

4. 扩展一下第三点，可以发现，任何一个满足条件的排列都有一个共同点：相邻的两个数奇偶性必然不同，原因是：两个奇数之和或者两个偶数之和都是偶数，而偶数一定不是素数，所以在选取当前元素的时候，比较一下它和前一个元素的奇偶性。再做决定，可以减少一部分计算量。

由 于奇数 + 偶数 = 奇数, 而奇数的二进制表示中,最低位是1, 所以有下面的代码, 其中curValue是当前值, a[lastIndex]是前一个值.

[C#] 纯文本查看 复制代码

1 if(!((curValue + a[lastIndex]) & 1)) // 相邻的数奇偶性必然不同
2     return false ;

经过上面的优化，代码如下，应该会比原来快很多。还有什么地方可以优化么？欢迎讨论！

[C#] 纯文本查看 复制代码

代码

Code highlighting produced by Actipro CodeHighlighter (freeware)[url=http://www.CodeHighlighter.com/-->]http://www.CodeHighlighter.com/-->[/url] 1 #include <iostream>
using namespace std ;

// 小于37的所有素数
int prime[38] = 
{
    0, 0, 1, 1, 0, 1, 0, 
    1, 0, 0, 0, 1, 0, 1, 
    0, 0, 0, 1, 0, 1, 0, 
    0, 0, 1, 0, 0, 0, 0, 
    0, 1, 0, 1, 0, 0, 0,
    0, 0, 1,
} ;

// 输出一个解
void Output(int a[], int n)
{
    for(int i = 0; i < n; i++)
        cout << a << " " ;
    cout << endl ;
}

// 判断当前序列是否满足条件
bool IsOk(int a[], int lastIndex, int curValue)
{
    if(lastIndex < 0) // 第一个元素没有前驱元素，返回真
        return true ;

    if(!((curValue + a[lastIndex]) & 1)) // 相邻的数奇偶性必然不同
        return false ;

    if(!prime[a[lastIndex] + curValue]) //相邻元素和为素数
        return false ;

    for(int i = 0; i <= lastIndex; i++) // 去重，curValue没有出现过
        if(a == curValue)
            return false ;

    return true ;
}

void PrimeCircle(int a[], int n, int t)
{
    if(n & 1) // 奇数无解，直接返回
        return ;

    if(t == n) 
    {
        if(prime[a[0] + a[n - 1]]); // 判断首尾元素
            Output(a, n) ; 
    }
    else
    {
        for(int i = 1; i <= n; i++)
        {
            a[t] = i ;
            if(IsOk(a, t - 1, i)) //如果当前元素满足条件
                PrimeCircle(a, n, t + 1) ; //进行下一次递归
        }
    }
}

int main(void)
{
    int a[20] ;
    const int n = 4 ; // 4个元素的排列
    PrimeCircle(a, n, 0) ;
    
    system("pause") ;
    return 0 ;
}