紫书例题7-4 素数环

Posted on | In |

素数环问题：从1到n(n<=10000)这n个数摆成一个环，要求相邻的任意两个数的和是一个素数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <algorithm>
#include <string>
#include<iostream>
int a[1000];
using namespace std;
bool isnotPrime(int n){
	for(int i=2;i<n;i++)
	if(n%i==0) {
		return true;
	}
	 return false;               
}
int main()
{
	int n;
    cin>>n;
    for(int i=0;i<n;i++) a[i]=i+1;
    do{
	int flag=1;
    for(int i=0;i<n;i++){//!!括号的起止地方 

    	if(isnotPrime(a[i]+a[(i+1)%n])) {//!!逻辑问题 
    	flag=0;
    	break;
    	}
	}
    if(flag==1) 
	{
		for(int i=0;i<n;i++)
		cout<<a[i]<<" ";
			cout<<endl;
	}
}while(next_permutation(a+1,a+n));//!!审题 输出时从整数1开始逆时针排列 
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <algorithm>
#include <string>
#include<iostream>
# include<math.h>
int a[100]; 
int vis[100]={0};
int n;
using namespace std;
bool isnotPrime(int n){
	for(int i=2; i <= sqrt(n);i++)
	if(n%i==0) {
		return true;
	}
	 return false;               
}
void dfs(int cur){
	if(cur==n&&!isnotPrime(a[n-1]+1))
	{
		for(int i=0;i<n-1;i++)
		cout<<a[i]<<" ";
		cout<<a[n-1]<<endl;
	 } 
	else for(int i=2;i<=n;i++){//!!!6
		if(!vis[i]&&!isnotPrime(a[(cur-1)%n]+i))
		{a[cur]=i;
		vis[i]=1;
		dfs(cur+1);
		vis[i]=0;
			
		}
		
	}
	
}
int main()
{ a[0]=1; 
  int i=0;
while(scanf("%d",&n)!=EOF && n!=0)
    {
    	i++;
   printf("Case %d:\n",i);
    dfs(1);
   
	} return 0;
}

参考链接

https://blog.csdn.net/C20190413/article/details/72630756
https://blog.csdn.net/MosBest/article/details/69085525