質量数環問題の2種類の解法と最適化の構想

今学期のコンピュータシステムの実験の課程の中で質数の環の問題に出会って、プログラムを編纂して解いてそしてARMの多核の開発システムの上で実験を展開する必要があります.以下は私が検索して得た2つの解法で、1つ目はC言語で作成され、20個の数字の質量ループしか出力できません.第2の解法はC++で記述され,20個以下の数の素数ループを出力できる.
解法1:

//        n              ，         ，         。
//p[i][j]      i   j       ，f[i]     i     ，
//T[i]             i             P[i][]    。
// F[i][j]                   i      j   ，
//  ：F[1][2]       1           ，          P[][]           0
// ，               F[1][2] ， F[1][2] = 4。
//             F[][]，            C[]        ，          F[][]   ，
//                 。              ，            C[]   ，
//                          ，             C[] ，
//                   ，       。         C[] ，  
//    ，      ，           。
#include"stdafx.h"
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
void main()
{
   int  P[21][21], F[21][21], f[21], T[21], C[20];   //20  
   int i, j, k, t, temp, p, flag, n, c;
   double duration;
   clock_t start, finish;
   start = clock();
   n = 20;
   c = 20000;
   for(i = 1; i <= n; i++)
   {
	   k=1;
	   for(j = 1; j <= n; j++)
	   {
		   P[i][j] = 0;                              //     
		   F[i][j] = 0;
		   if(j != i && ((int)abs((i-j) % 2)) != 0)  //i j    
		   {
			   temp = i + j;
			   t = (int) sqrt((double)(temp) + 1);// i j     
			   for(p = 2; p <= t; p++)
			   {
				   P[i][j] = 0;
				   if(! (temp % p)) break;     //  temp     ，  temp   ， P[i][j] 1
				   P[i][j] = 1;                      
			   }
		   }
		   if(P[i][j])                               //  i j      
		   {                                         //     i      k   j
			   F[i][k] = j;                          
			   k++;
		   }
	   }
   }
   
   //for(i = 1; i <= n && c; i++)
   for(i=1; i<=n; i++)
   {
	   C[0] = i;
	   for(p = 1; p <= n; p++)
	   {
		   T[p] = 1;                                 //T[i]             i             F[i][]    。
		   f[p] = 0;                                 //f[i]    i     ，0      ，1     
	   }
	   f[i] = 1;
	   k = 1;
	   while(k)
	   {
		   while(F[i][T[i]] && k < n)               //F[i][T[i]]     i               i  
		   {
			   if(! f[F[i][T[i]]])              //f[F[i][T[i]]]      F[i][T[i]]     
			   {
				   C[k] = F[i][T[i]];        //        
				   f[C[k]] = 1;
				   T[i]++;
				   i = C[k];
				   k++;
			   }
			   else;
			   T[i]++;
		   }
		   if(k == n)                               //  C[0] C[n-1]       
		   {
			   temp = C[0] + C[n-1]; 
			   t = (int) sqrt((double)(temp) + 1);
			   for(p = 2; p <= t; p++)
			   {
				   flag = 0;
				   if(! (temp % p)) break;
				   flag = 1;                 //  C[0] C[n-1]     ， flag 1
			   }
			   if(flag)
			   {
				   c--;
				   for(p = 0; p < n; p++)
				   {
					   printf("%d- ",C[p]);
				   }
				   printf("
");
			   }
		   }
		   
		   f[C[--k]] = 0;                       //  
		   T[C[k]] = 1;
           i = C[k-1];
	       if(!c)                                  //  c 0， k 0，    while  ，     20000    
			   k=0;
	   }//end while
   }//end for
   finish=clock();
   duration = (double)(finish - start) / CLOCKS_PER_SEC; 
   printf( "%f seconds
", duration ); 
}//end main

解法2:

/*********************************************************************** 

  : 

1、     1  ，    a[0]  1. 

2、        ，             ，        bUsed[]     . 
3、                   ，       (              )。 
************************************************************************/  
#include "stdafx.h"
#include <iostream>  
#include <math.h>  
using namespace std;  
int n=0;
int a[20];  
bool bUsed[20];//    a[20],               (   )      
  
/*     */  
bool isp(int n){  
    if(n<3)  
        return false ;  
    int len=(int)sqrt(n+0.0);  
    for (int i=2;i<=len;i++){  
        if(n%i==0)  
            return false ;  
    }  
    return true;  
}  
  
/*         */  
void AA(int cur){  
    //       ,           
    if(cur==n&&isp(a[0]+a[n-1])){  
        for (int i=0;i<n;i++)  
            cout<<a[i]<<' ';  
        cout<<endl;  
        return ;  
    }  
    // n-1   ,          ,                
    else for (int i=2;i<= n;i++){  
        if(!bUsed[i]&&isp(i+a[cur-1]))
{ 
//   i    ,               
            a[cur]=i;       // i       
            bUsed[i]=true;  //              
            AA(cur+1);      //     , cur+1<n        ,          
            //         n-1   1        
            bUsed[i]=false; //    ,                 
        }  
    }  
}  
  
int main(){  
    for (int i=0;i<20;i++)  
        a[i]=i+1;           //       1,2,3,4...  
    memset(bUsed,0,sizeof(bUsed));//      false         
    while (cin>>n,n){  
        AA(1);              //        ,         
    }  
}  

最適化の考え方:いくつかのルールで枝を切ることができ、検索効率を高めることができます.
1、入力nに対して、入力nが奇数であれば、条件を満たす素数リングがない.

if(n & 1) //     ，    
    return ;

2、隣接する2つの数のパリティは必然的に異なる.

 if(!((a[0] + a[n-1]) & 1)) //            
     return false ;