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

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * 신기한 소수 : 에라토스테네스의 체 => 시간 초과!!
 * @author SSAFY
 *
 */
public class Main {

	static int n;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		int arr[] = {2,3,5,7};
		for(Integer i : arr)
			recur(1,i);
		
	}
	
	public static void recur(int length, int num) {
		if (length == n) {
			System.out.println(num);
			return;
		}
		
		for(int i=1; i<=9; i++) {
			int new_num = num*10 + i; // 한자리 덧붙히D기
			if (isPrime(new_num)) { // 만약 해당수가 소수라면
				recur(length+1, new_num); // 붙여서 재귀호출
			}
		}
	}
	
	public static boolean isPrime(int num) {

		for(int i=2; i<=Math.sqrt(num); i++) {
			if (num%i == 0)
				return false;
		}
		return true;
	}

}

 

에라토스테네스의 체로 모든 소수를 다 구했더니 처참히 시간초과…!

Dfs를 통해 한자리씩 늘리고, 만약 늘려서 새로 만든 숫자가 소수라면 재귀로 새로운 숫자를 넘기는 방식으로 구현하였다.

재귀함수내에서 종료조건으로 숫자의 길이가 n을 만족한다면, 해당 숫자를 출력하고 리턴한다.

- for문을 1~9까지 돌리는 이유는 끝자리에 0이들어간 숫자는 절대 소수가 될 수 없기 때문이다.

 

소수판별 함수는 다음과 같다. x*y 곱셈은 쌍을 이루기 때문에 Num의 제곱근까지만 탐색해도 된다.

 

Main() 에서 해당 재귀를 호출할 때는, 불필요한 연산을 줄이기 위해 2,3,5,7 소수들만 시작 숫자로 호출한다.