문제

입력

출력

예제

idea

난 진짜 이 문제만 생각하면 울고싶다.
알고리즘이 이런거구나 라고 뼈저리게 느끼게 되었다.
처음에는 1~pow(10,N)까지 입력된 자리값까지 반복문을 실행하며 마지막 끝자리를 확인하여 앞자리가 2, 3, 5, 7 인 수만 계산하게 하였고 그 범위 내에서 소수인 수를 N만큼 반복문을 또 실행하여 뒷자리를 하나씩 잘라 소수 판별을 하도록 하였다. 말로 설명해도 복잡해보이는데 이러니 당연히 시간 초과가 나오지..

결국 이 문제를 푼 지인에게 도움을 청한 결과 알고리즘을 알아낼 수 있었다.
이 문제는 결국 자리수 만큼의 수를 /10을 한 몫이 모두 소수라는 점이 키 포인트였다.
그래서 생각한 알고리즘은 숫자가 적을 때 부터 소수인 수를 자리수에 맞게 늘려나가며 계산하는것이다
예를 들어
처음 숫자가 2일 때 2는 소수이기 때문에 맨 앞자리가 2가 될 수 있다.
그러면 10을 곱해주어 20~29의 숫자를 또 판별한다.
그 중 소수인 수들을 또 10을 곱해주어 230~239, 290~290 을 판별한다.
이런식으로 소수인 수만 점점 저장해 나간다.

정리

맨 앞자리는 소수여야함.
2,3,5,7
소수에서 10을 곱해준 수들 중 소수인 수를 또 판별함
그렇게 자리값에 맞게 반복해줌
이렇게 계산을 하면 모든 자리에서 소수인 수를 구할 수 있음.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int num;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		long startTime = System.currentTimeMillis();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		num = N;

		for (int i = 0; i < 10; i++) {
			if (i == 2 || i == 3 || i == 5 || i == 7) {
				func(i);
			}
		}

		System.out.println(sb);
	}

	public static void func(int x) {

		x *= 10;
		if (x < Math.pow(10, num)) {
			for (int i = 0; i < 10; i++) {
				if (TF(x + i) == 1)
					func(x+i);
			}
		} else
			sb.append(x/10).append("\n");
	}

	public static int TF(int x) {

		for (int i = 2; i <= Math.sqrt(x); i++) {
			if (x % i == 0)
				return 0;
		}
		return 1;
	}
}

결과