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

🖥️ 문제

 

 

 

🎓  문제 풀이

입력으로 신기한 소수의 자릿수가 주어진다.

10미만의 소수는 2,3,5,7이 있으므로 소수를 미리 배열에 정의했다.

왼쪽에서부터 시작하여 n자릿수가 되기까지의 숫자가 전부 소수가 

되어야함을 유의하여 풀어야한다.

 

🚨CODE

import java.io.*;
import java.util.*;

public class Main {
	static String[] prime = {"2","3","5","7"};
	static int n;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws Exception  {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		n = Integer.parseInt(br.readLine());
		
		for(int i = 0; i<prime.length; i++) {
			dfs(prime[i], 1);
		}
		
		System.out.println(sb);
	}
	public static void dfs(String num, int len) {
		if(len == n) {
			if(isPrime(num))
				sb.append(num).append("\n");
			return;
		}
		
		for(int i = 0; i<=9; i++) {
			if(!isPrime(num+i))
				continue;
			dfs(num+i, len+1);
			
		}
		
	}
	public static boolean isPrime(String str) {
		int primeNum = Integer.parseInt(str);
		for(int i = 2; i <= primeNum/2; i++) {
			if(primeNum % i == 0)
				return false;
		}
		return true;
	}
}