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

[백준]2023: 신기한 소수

www.acmicpc.net/problem/2023

2023번: 신기한 소수

풀이

N자리 수중에 소수를 모두 출력하는 DFS문제이다. 숫자를 자리수 별로 하나씩 뽑으면서 뽑았을 때 소수가 되는 경우만 수를 이어서 뽑는다. 뽑다가 N자리가 되는 순간 출력을 하도록 하였다.

 

소수를 판별하는 방법은 에라토스테네스의 접근 방식을 사용했다. 소수 판별식 코드는 아래와 같다.

public 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;
}

이때 num의 제곱근을 범위로 사용하는 이유는 아래와 같당.

모든 수를 두 수의 곱으로 표현했을 때 각각의 두 수 중에 하나는 반드시 제곱근보다 작거나 같다. 

예를들어, num이 10일때 2 * 5로 표현할 수 있으며 10의 제곱근은 3.16...이 된다. 이때 10이 2로 나누어 지는지 확인을 했다면 5로 나누어 지는지는 더이상 확인하지 않아도 된다. 

결국에 연산을 더 빠르게 하기 위해 제곱근을 사용하는 것이다.

 

코드

import java.util.*;
 
public class Main {    
    
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        dfs(0, "", n);
        System.out.println(sb.toString());
    }    
    
    public static void dfs(int idx, String num, int n) {
        if(idx == n) {
            sb.append(num + "\n");
            return;
        }
        
        for(int i = 1; i <= 9; i++) {
            if(isPrime(Integer.valueOf(num + i))) dfs(idx + 1, num + i, n);
        }
    }
    
    //에라토스테네스의 소수 판별 방식 사용.
    public 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;
    }
}