2023 신기한 소수

어떤 소수가 뒤에서 부터 한숫자씩 끊어내도 계속 소수일 때 이것을 신기한 소수라고 한다. N 자리 숫자중에 신기한 소수를 출력하는 문제이다.

신기한 소수를 예로 들면, 7331 은 소수이고, 733도 소수, 73도 소수, 7도 소수이다.

이 문제는 재귀로 해결이 가능하고 순서는 다음과 같다.
1. 1의자리 소수를 구한다. 1의 자리 소수는 2,3,5,7이 있다.
2. 이 숫자를 가지고 작은것부터 시작해서 재귀를 한다. 재귀는 현재 숫자와 현재 자리수를 같는다.
3. 재귀를 하면 현재 숫자의 뒤에 0~9까지 숫자를 붙여서 소수인지 판별한 다음, 소수라면 길이가 N이 될때까지 재귀한다.

소스