2023 - 신기한 소수

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Main {

    static int N;
    static ArrayList<Integer>[] magicPrimes = new ArrayList[9];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());

        for (int i = 0; i <= N; i++) magicPrimes[i] = new ArrayList<>();
        magicPrimes[1].add(2);magicPrimes[1].add(3); magicPrimes[1].add(5); magicPrimes[1].add(7);

        for(int i=2; i<=N; i++){
            for(int prime : magicPrimes[i-1]){
                for(int j=1; j<=9; j+=2){
                    int newNum = prime*10 + j;
                    if(isPrime(newNum)){
                       magicPrimes[i].add(newNum);
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();

        for(int prime : magicPrimes[N])
            sb.append(prime).append("\n");


        System.out.println(sb);
    }

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

• 일종의 백트래킹
• N자릿수의 신기한 소수를 만족시키기 위해서는 반드시 N-1번째 자릿수의 신기한 소수를 사용해서 만들어야 한다.
  • 추가적으로 한자릿수를 제외하면 나머지는 짝수이면 절대 소수 아니라서 짝수인 경우 제외하고 홀수인 경우만 에라토스테네스로 체크한다.