https://www.acmicpc.net/problem/2023
2023번: 신기한 소수수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수www.acmicpc.net
와 이전에 풀때 포기했던 문젠데, 백트래킹을 해보고 왔더니 정말 쉬운 문제였다.
먼져, 첫자리는 소수여야하므로 2,3,5,7이외의 수는 없다.
2,3,5,7을 시작으로 하는 n자리의 숫자를 찾으면 되는데,
한단계씩 지나갈때마다 그 단계의 신기한 소수판별을 하고, 아니면 더이상 탐색하지 않는다.
신기한 소수를 판별할 때, 그 자리만 판별한다.
ex 길이가 3일때, 길이가 1,2인 경우는 앞에서 했으므로, 3인 경우만 판별하면 끝
기분좋게푼 문제였다.
def check(strnum): num=int(strnum) if num%2==0: return False
for i in range(3,int(num**0.5)+1,2): if num%i==0:
return False return Truefirst=['2','3','5','7',]
def dfs(strnum): # str if len(strnum)==n: print(strnum) return
for i in (1,3,5,7,9): tmp=strnum+str(i) if check(tmp):
dfs(tmp)n=int(input())for start in first: dfs(start)