문제

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

“이제 슬슬 비번 바꿀 때도 됐잖아”
“응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
“그럼 8179로 해”
“흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
“흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
“귀찮아”
그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

입력

첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.

출력

각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.

풀이

모든 소수들을 먼저 찾아 준 다음 첫번째 숫자를 4자리를 모두 0~9까지의 숫자로 바꿔본다 -> 이 숫자가 소수이면 heapq 에 넣어서 계속 진행할 수 있게 됩니다.

import sys
sys.stdin = open('input.txt')
import heapq


# 소수 찾기
prime = [True]*10000    # 10000까지의 수중에
for i in range(0,1000): # 네자리 미만은 소수가 아니다 표시
    prime[i]=False

for i in range(2,10001):    # 2부터 10000까지 돌면서
    for j in range(2,9999//i+1): # 10000까지의 i의 배수들을(2부터시작)
        prime[i*j]= False       # 소수 탈락시킨다.


def bfs(a,b):           # 시작점 끝점이 들어온다.
    visited = [10000]*10000 # 최소거리를 찾기 위한 visited (큰수)
    visited[a]= 0           # 시작점 0
    Q = []
    heapq.heappush(Q,[0,a])

    while Q :
        count,a = heapq.heappop(Q)  # 바뀐횟수, 현재 숫자 를 pop
        intA = list(str(a))         # 현재 숫자를 문자열화 해준다.

        if a==b:                    # a==b 같으면 끝낸다
            print(count)
            return

        for i in range(4):          # 네자리를 돌면서 [a b c d]
            for j in range(10):     # 그 숫자들을 0~9 까지의 숫자들로 바꿔준다.
                this=""             # 빈 문자열을 만들고
                for k in range(4):  # a의 자리를 하나씩 추가해주는데 i번째 숫자는 j로 바꿔준다.
                    if k ==i :
                        this+= str(j)
                    else:
                        this+= intA[k]

                if prime[int(this)] and count<visited[int(this)]:   # 이 숫자가 소수이면서 현재 count 보다 작다면
                    visited[int(this)]=count                        # 방문해주고 , Q에 넣어준다.
                    heapq.heappush(Q,[count+1,int(this)])


tc = int(input())
for _ in range(tc):
    a,b = map(int,input().split())
    bfs(a,b)