[JAVA]백준 2023번 신기한 소수

📌문제 링크

---

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

📌문제 설명

---

백트래킹으로 숫자를 뒤에 하나씩 붙여나가면서 소수판별 후 출력해주면 됩니다. 시간제한이 넉넉해서 최적화까진 필요없는 문제입니다.

📌코드

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static ArrayList<Integer> primeNumLIst = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        input();
        solve();
    }

    public static void input() throws Exception {
        N = Integer.parseInt(br.readLine());
    }

    public static Boolean checkPrimeNum(int num) {
        if(num == 1) return false;
        for(int i = 2; i < num; i++) {
            if(num % i == 0) return false;
        }
        return true;
    }

    public static void backTracking(int cnt, int num) {
        if(cnt == N) {
            primeNumLIst.add(num);
            return;
        }
        for(Integer i : new int[]{1, 3, 7, 9}) {
            if (checkPrimeNum(num * 10 + i)) {
                backTracking(cnt + 1, num * 10 + i);
            }
        }
    }

    public static void solve() throws Exception {
        backTracking(1, 2);
        backTracking(1, 3);
        backTracking(1, 5);
        backTracking(1, 7);
        for (Integer integer : primeNumLIst) {
            bufferedWriter.write(integer + "\n");
        }
        bufferedWriter.flush();
        bufferedWriter.close();
    }
}