DFS 문제 풀이 소수고리문제 파이썬

http://book.interpark.com/product/BookDisplay.do?_method=detail&sc.shopNo=0000400000&sc.prdNo=201620016&sc.saNo=003002001&bid1=search&bid2=product&bid3=title&bid4=001

정보올림피아드를 준비하는 초중고생을 위한 알고리즘 하성욱

책을 보고있구요

내가푼 답만 올리는건 저작권에 괜찮겠지?????

다들 PS는 c++로 하던데

c를 쓴지가 2년이 넘어서....

c로는 나중에 짜보고

일단은 python으로 풀어보는중 ㅠㅠㅠㅠㅠㅠ 

소수고리 문제

책이랑 비슷한 문제인거 같은데 같은 문제인지 안읽어봄 : http://khgkjg12.blogspot.kr/2016/08/uva-514-c.html (문제)

N_rings = 8is_prime=[True for i in range(32)]
possible_rings = []
for i in range(2,17) :
    if is_prime[i] is True:
        for j in range(2, int(32/i)):
            is_prime[i*j] = Falsedef DFS(ring_list):
    if len(ring_list) == N_rings :
        if is_prime[ring_list[-1]+1]:
            possible_rings.append(ring_list)
        return    for next_i in range(2, N_rings+1):
        if next_i not in(ring_list) and is_prime[ring_list[-1]+next_i]:
            DFS(ring_list+[next_i])

DFS([1])

print(possible_rings)