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

2023번: 신기한 소수

---

 

• 생각

DFS를 통해 N자리의 각 자리 모두 소수인 숫자만 추가해주었다.

 

• 코드

 

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

public class Main {
	static int N;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(sb.toString());
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		sb = new StringBuilder();

		dfs("");
	}

	private static void dfs(String s) {
		if (s.length() == N) {
			sb.append(s + '\n');
			return;
		}
		for (int i = 1; i <= 9; i++) {
			if (Prime(Integer.parseInt(s + i))) {
				dfs(s + i);
			}
		}

	}

	private static boolean Prime(int num) {
		if (num == 1)
			return false;

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