Caioj 1040:素数圈

0x01


  1. 判断素数
  2. 简单dfs

0x02


代码:
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int n,a[110],cnt;// a[] 储存顺序 cnt 临时储存和
bool x[110];//x[] 判重
// 判断质数
bool zs(int x){
    for(int i=2;i<=sqrt(x)+1;i++){
        if(x%i==0) return false;
    }
    return true;
}
// dfs部分
void dfs(int k){
    if(k==n+1){// 到达最终步骤
        if(!zs(a[n]+a[1])) return ;// 如果不是质数,那么下地狱吧
        // 输出
                for(int i=1;i<=n;i++){
            printf("%d ",a[i]);
        }
        printf("\n");
    }
    else{
        for(int i=2;i<=n;i++){
            if(!x[i]){
                cnt=a[k-1]+i; //求这个数与上个数的和
                if(zs(cnt)){// 求质数
                    a[k]=i;
                    x[i]=true;
                    dfs(k+1);
// 回溯
                    x[i]=false;
                    a[k]=0;
                }
            }
        }
    }
}
int main(){
// 输入
    scanf("%d",&n);
    a[1]=1;
    x[1]=true;
    dfs(2);// 目前已经确定第一个数为1(不然会重复)
}
]]>

4 thoughts on “Caioj 1040:素数圈

  • 我去发现你把我的站名搞错了,大佬我要杀了你<成功混过实名>

    1. 别别别,求饶命,我改过来了

      1. 额还是错了,大佬是堆栈的栈~今天Gravatar有毒啊,竟然炸了

        1. 不知道Gravatar每天都在发生什么,这回应该对了

    发表评论

    邮箱地址不会被公开。 必填项已用*标注

    message
    account_circle
    Please input name.
    email
    Please input email address.
    links