링크

2023 신기한 소수

문제

풀이

처음에 무지성 dfs를 돌렸지만 시간초과가 나서 더 효율적으로 풀어야 겠다고 생각했다.
수를 1의자리부터 1000의자리까지 올라가면서 만약 다 소수라면 값을 출력하도록 만들었다.

예를 들어서 7331을 보자면 처음에 0부터 9까지 탐색하면서 1000의자리인 7이 소수이므로 dfs를 통해 100의자리를 찾는다. 그리고 73이 소수에 걸리면서 또 10의자리를 찾고 이런식으로 쭉쭉 찾아나간다.
코드를 보면 쉽게 이해할 수 있다.

코드

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

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static List<Integer> list = new ArrayList<>();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		dfs(0, n, 0);
		System.out.println(sb.toString());
	}
	
	public static void dfs(int dept, int limit, int number) {
		if(dept == limit) {
			sb.append(number + "\n");
			return;
		}
		
		
		for(int i=0;i<10;i++) {
			if(dept == 0 && (i == 0 || i == 1)) continue;
			
			int num = 10 * number + i ;
			if(isPrime(num)) {
				dfs(dept+1, limit, num);
			}; 
		}
	}
	
	public static boolean isPrime(int number) {
		for(int i=2;i<=Math.sqrt(number);i++) {
			if(number % i == 0) return false;
		}
		
		return true;
	}
	
}