신기한 소수 [백준 2023][골드5][Java]

 

[광고 누르면 오늘의 행운 상승!!]

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

2023번: 신기한 소수

8자리수 까지 구해야 하기 때문에 전부 돌면 시간초과가 난다.

자리수 마다 소수인지 구별하고 소수가 맞으면 더해주었다.(백트래킹)

제곱근을 구해서 2~제곱근 까지의 숫자중 나누어 떨어지는 것이 있으면 소수가 아니다. 

import java.util.*;


public class 신기한소수 {
	public static StringBuilder sb = new StringBuilder();
	public static int N;
	
	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		N = sc.nextInt();
		 
	    dfs("", 0);
	    System.out.println(sb);
	}
	
	public static void dfs(String s, int cnt) {
		if(cnt == N) {
			sb.append(s + "\n");
			return;
		}
		for (int i = 1; i <= 9; i++) {
			if(isPrimeNumber(Integer.parseInt(s+i))) {
				dfs(s+i, cnt +1);
			}
		}
	}
	public static boolean isPrimeNumber(int num) {
		if(num == 1) return false;
		
		int sqrt = (int)Math.sqrt(num);
		for (int i = 2; i <= sqrt; i++) {
			if(num%i == 0) return false;
		}
		return true;
	}
}