신기한 소수

문제

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

예제 입력 1 복사

예제 출력 1 복사

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        DFS(2,1, N);
        DFS(3,1, N);
        DFS(5,1, N);
        DFS(7,1, N);
    }   
    // DFS
    public static void DFS(int num, int jarisu, int N){
        if(jarisu == N && isPrime(num)){
            System.out.println(num); // N자리수를 만족하고 소수라면 해당 값 출력
        }

        int[] nextPrime = {1,3,7,9}; // 그 다음에 붙을 소수 후보들

        for(int next : nextPrime){
            if(isPrime(num * 10 + next)){
                DFS(num * 10 + next, jarisu + 1, N);
            }
        }
    }

    // 소수인지 판별하는 함수
    public static boolean isPrime(int num){
        // 1은 소수가 아니다.
        if(num < 2) return false;

        // 그 외 숫자 : 2 ~ sqrt(num)까지 나눠떨어지는 수가 있다면 false
        for(int i=2; i<Math.sqrt(num); i++){
            if(num % i == 0) return false;
        }
        // for문을 다 순회하는데 성공했다면 소수이다.
        return true;
    }
}

소수판별

1은 소수가 아니므로 제외.
2부터 √N 까지 반복하면서 나눠떨어지는지 확인.
나눠 떨어지면 false, 아니면 true 반환.

DFS

들어온 숫자, 현재 자리수, 목표 자리수를 입력으로 받는다.
만약 현재 자리수가 목표자리수 N을 만족하고 소수라면 값 출력
1번째 자리수는 2,3,5,7 이 들어올 수 있다. 따라서 애초에 DFS실행할때, 2,3,5,7을 입력값으로 주어 DFS탐색을 시작한다.
2번째 자리부터는 2,5이면 소수가 될 수 없다.
2번째자리부터는 1,3,5,7과의 조합이 소수후보가 된다.
for문을 돌면서 조합을 해본 후 새로운 값이 소수라면 해당 값을 가지고 다시 DFS문으로 들어간다.