백준 2023번 신기한 소수 (Java)

문제

백준 2023번 신기한 소수 / 골드5
수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.
7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.
수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

입력

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

풀이

소수를 찾는 문제이다. 일반적으로 소수 판별에는 에라토스테네스의 체를 이용하는 방법이 있다. 하지만, N자리의 숫자 중에서 신기한 소수를 판별하므로 DFS를 사용해 풀이를 해보았다.

소수를 판별하는 isPrime 함수는 입력된 수num을 2부터 num의 제곱근까지 나눈 나머지가 0이 나오지 않을 경우, 소수로 판별하도록 만들었다.

신기한 소수를 찾기 위해서 dfs 함수 내부에서는 1자리 소수인 2, 3, 5, 7을 시작으로 오른쪽에 자리수를 추가해 주며, 만들어진 수가 소수인지 판별하며 소수인 수만 N자리 수가 될 때까지 같은 작업을 반복하는 방법으로 문제를 해결했다.

코드

import java.util.Scanner;

public class Main {

    static int N;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        dfs(2, 1);
        dfs(3, 1);
        dfs(5, 1);
        dfs(7, 1);
    }

    static void dfs(int num, int exp) {
        if (exp == N) {
            if (isPrime(num)) {
                System.out.println(num);
            }
            return;
        }

        for (int i = 1; i <= 9; i++) {
            if (i % 2 == 0) {
                continue;
            }
            int nextNum = (num * 10) + i;
            if (isPrime(nextNum)) {
                dfs(nextNum, exp + 1);
            }
        }
    }

    static boolean isPrime(int num) {
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}