[Algorithm] 백준 2023 - 신기한 소수 (JAVA)

https://www.acmicpc.net/problem/2023

import java.util.Scanner;

public class Main {
    static int[] prime;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int min = (int) Math.pow(10, n-1);
        int max = (int) Math.pow(10, n);
        prime = new int[max];
        isPrime(max);
        for (int i = min; i < max; i++) {
            if(prime[i] == 0) {
                if (chk(i)) System.out.println(i);
            }
        }
    }

    public static boolean chk(int num) {
        sb.setLength(0);
        sb.append(num);
        int cnt = sb.toString().length();
        if (cnt == 1 && prime[num] == 0) {
            return true;
        }
        else {
            for (int i = 0; i < cnt; i++) {
                String word = sb.substring(0, sb.length()-i);
                int n =Integer.parseInt(word);
                if(prime[n] == 1) return false;
            }
            return true;
        }
    }
    public static void isPrime(int max) {
        prime[0] = prime[1] = 1;
        for (int i = 2; i < max; i++) {
            if (prime[i] == 0) {
                for (int j = i * 2; j < max; j += i) {
                    prime[j] = 1;
                }
            }
        }
    }

}

• n 의 값을 입력받아 최솟값, 최댓값을 구하여 최댓값 만큼 에라토스테네스의 체를 사용한 후 소수일 때 자릿수별 팰린드롬을 구하려고 했지만, 정답은 맞으나 메모리 초과 문제가 발생했다. 아마 8일 때 연산이 많아져 발생하는 것 같다.

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

public class Main {
    static int n;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dfs("", 0);
        System.out.println(sb.toString());
    }

    static void dfs(String str, int num) {
        if (num == n) sb.append(str).append("\n");
        else{
            for (int i = 1; i <= 9; i++) {
                String word = str + i;
                if (isPrime(Integer.parseInt(word))) dfs(word, num+1);
            }
        }
    }

    static boolean isPrime(int k) {
        if (k == 1) return false;
        for (int i = 2; i * i <= k; i++) {
            if (k % i == 0) return false;
        }
        return true;
    }
}

• 에라토스테네스의 체를 사용하지 않고, dfs로 소수일 때만 다음 자릿수를 탐색 하여 가지치기를 하도록 하니 성공.