当前位置：首页 > news >正文

素数环

news 2025/6/6 10:03:37

题目描述
给定 n (n<=20) 把 1~n的n个数组成一个环，使得相邻的两个数和都是素数，如果不存在输出no solution

输入
一个n （ 2<=n<=20）

输出
输出这n个数，使得相邻的两个数都是素数，如果不存在输出no solution

样例输入
4

样例输出
1 2 3 4

提示
如果存在多组，请输出字典序最小的那个

分析:
DFS+剪枝
当N为奇数时，则数字1、2、…、N中数字为奇数的个数比偶数的个数多一个，必定存在两个奇数相邻的情况，奇数+奇数=偶数，不符合素数环的条件。
当N个数能组成素数环时，则数字1必定在素数环中的某个位置，将数字1移到素数环第一个位置，相当于将素数环旋转，依旧是一个素数环，因此可设素数环第一个数字为1，由此结合DFS可以推出字典序最小的素数环。

代码(C++）

#include<bits/stdc++.h>
using namespace std;
bool Prime(int n);
void DFS(int cnt,int n);
bool Flag=false;
bool Index[21];
bool flag[40];
int ans[21];
int main() {int n;cin>>n;fill(Index,Index+21,false);fill(flag,flag+40,false);for(int i=1; i<40; i++)flag[i]=Prime(i);ans[0]=1;Index[1]=true;if(n%2==0){DFS(1,n);}if(!Flag) {cout<<"no solution"<<endl;;}return 0;
}
bool Prime(int n) {if(n==1)return false;for(int i=2; i*i<=n; i++)if(n%i==0)return false;return true;
}
void DFS(int cnt,int n) {if(Flag)return;if(cnt==n&&flag[ans[cnt-1]+ans[0]]) {for(int i=0; i<cnt; i++)cout<<ans[i]<<" ";Flag=true;}for(int i=1; i<=n; i++) {if(!Index[i]&&flag[i+ans[cnt-1]]) {ans[cnt]=i;Index[i]=true;DFS(cnt+1,n);Index[i]=false;}}
}

代码(Java）

import java.util.Scanner;
public class Main {static boolean Flag=false;public static void main(String[] args) {Scanner cin = new Scanner(System.in);int n=cin.nextInt();boolean[] index=new boolean[21];boolean[] flag=new boolean[40];int[] ans=new int[21];int cnt=0;for (int i=1;i<flag.length;i++){flag[i]=Prime(i);}if(n%2==0){ans[0]=1;index[1]=true;DFS(1,n,ans,index,flag);}if(!Flag){System.out.println("no solution");}}public static boolean Prime(int n){if(n==1)return false;for(int i=2;i*i<=n;i++){if(n%i==0)return false;}return true;}public static void DFS(int cnt,int n,int[] ans,boolean[] index,boolean[] flag){if(Flag)return;if(cnt==n&&flag[ans[cnt-1]+ans[0]]){for(int i=0;i<cnt;i++)System.out.print(ans[i]+" ");Flag=true;}for(int i=1;i<=n;i++){if(!index[i]&&flag[i+ans[cnt-1]]){ans[cnt]=i;index[i]=true;DFS(cnt+1,n,ans,index,flag);index[i]=false;}}}
}