[백준 2023] 신기한 소수(JAVA)

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

2023번: 신기한 소수

dfs로 문자열 뒤에 숫자를 붙여가면서 소수인지 체크해주었다.

소수인지 판별할 때 sqrt값을 사용하여 시간을 절약할 수 있었다.

 

sqrt를 사용하지 않을 경우 시간차이가 10배이상 증가.

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

public class Main {

	public static int N;
	public static boolean f;
	public 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());
		dfs("", 0);
		System.out.println(sb.toString());
	}

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

	private static boolean isPrime(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;
	}
}