素数环
- 素数环问题的介绍
- 素数环问题的算法分析
- 素数环问题代码实现
素数环问题的介绍
素数环指的是将从1到n这n个整数围成一个圆环，若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。我们以n=20，为例把1~20摆成一个环，想一想该如何排列呢？
素数环问题的算法分析
素数环问题其实就是我们在上节课提到的排列问题，我们当然可以利用回溯算法穷举出20个数所有排列的可能，然后找出符合条件的排列，但是这样的效率比较低。我们在排列的时候可以根据素数环的性质，作出筛选
从1开始，每个空位有20种可能，后面依次排列
每次排列时，与前面的数不同，与左边相邻的数和是一个素数
第20个数还需要判断是否和第一个数的和是否是素数
素数环问题的代码实现
因为是素数环，为了便于选择我们第一步，将第一个数字选定为1:
res=[0]+[1]+[0]*19 #第一步的结果是1存放在res[1],依次类推,res[0]存放当前找到多少个素数环
status=[False]*2+[True]*19 #status[i],表示数字i当前的状态，True是能够被选择，False代表不能被选择
def dfs(step):
if step>20 and prime(res[20],res[1]): #第20个数选择完毕，还需要判断是否和第一个数的和是否是素数
res[0]+=1
print(res)
return
for i in range(2,21):#从第二步开始，每一步从2~20中进行选择
if(prime(res[step-1],i) and status[i]): #当前选择与上一步选择之和要为素数，而且当前该数的状态可以选择
res[step]=i #保存当前结果
status[i]=False
dfs(step+1)
status[i]=True
def prime(x,y):#定义prime(x,y)函数，该函数的功能是判断两个整数的和是否是素数
s=x+y
for i in range(2,int((s)**0.5)+1):
if(s%i==0):
return False
else:
return True
dfs(2)#第一步已经选定，从第二步开始
事实上上述程序使用python执行完毕需要一定的时间，因为考虑顺逆时针1~20的素数环，一共6309300种，可以试一试上述程序执行所需的时间？
小结
根据素数环问题，理解回溯算法的思想
掌握素数环求解的回溯算法
习题
- 求解1~10的素数环问题
- 求解1~n的素数环个数，其中n=4~10,找一找素数环个数与n的关系