素数环问题 - 军军小站|张军博客

DFS，好像主要是对dfs的递归调用吧，自己也不太懂，

总之，它很神奇，多看看代码吧

<span style="font-size: 18px;">#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

int n;
int isp[100];
int vis[100]; 
int A[100];

int is_prime(int x)             //判断一个数是否为素数（该数比较小，不会引起超时） 
{
   int i=1,k;
   for(i=2;i<=(k=(int)sqrt(x));i++)
   if(x % i == 0)break;
   if(i<=k)return 0;
   else return 1;
    return x;
}

void dfs(int cur)                 //深搜寻路
{
     if(cur == n  &&  isp[A[0] + A[n-1]])  //递归边界，别忘了保证第一个和最后一个数，环结构
     {
         int i;
         printf("1");
         for(i=1;i<n;i++)
            printf(" %d",A[i]);    //打印方案 
         printf("\n"); 
     }
     else
     {
         int i;
         for(i=2;i<=n;i++)         //尝试放置每个数 i
         if(!vis[i]  &&  isp[i + A[cur-1]])    //如果 i 没有用过，且与前一个数之和为素数
         {
                A[cur] = i;
                vis[i] = 1;        //设置使用标志，表明用过
                dfs(cur + 1);
                vis[i] = 0;        //清除标记 
         } 
     } 
}

int main()
{
   int N,i;
   for(i=2;i<=200;i++)
      isp[i] = is_prime(i);              //生成素数表（较小范围的素数表，大范围的用素数筛法）
   while(scanf("%d",&N) == 1,N)
   {
       n = N;
       A[0] = 1;
       dfs(1);
   }
   return 0;
}
</span>

素数环问题

更多文章、技术交流、商务合作、联系博主

微信扫码或搜索：z360901061

微信扫一扫加我为好友

QQ号联系： 360901061

您的支持是博主写作最大的动力，如果您喜欢我的文章，感觉我的文章对您有帮助，请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧，狠狠点击下面给点支持吧，站长非常感激您！手机微信长按不能支付解决办法：请将微信支付二维码保存到相册，切换到微信，然后点击微信右上角扫一扫功能，选择支付二维码完成支付。

【本文对您有帮助就好】元

2元

5元

10元

20元

自定义