素数环 #

1. 素数环问题的介绍
2. 素数环问题的算法分析
3. 素数环问题代码实现

素数环问题的介绍 #

素数环指的是将从1到n这n个整数围成一个圆环，若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。我们以n=20，为例把1~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. 求解1~10的素数环问题
2. 求解1~n的素数环个数，其中n=4~10,找一找素数环个数与n的关系