[BJ2023] 신기한 소수

 

 백준 - 신기한 소수 

문제 링크

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

2023번: 신기한 소수

 

문제 입출력

4

2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

 

문제 풀이

package day220805.practice;


import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;


public class BJ2023_신기한소수 {
	static int N;
	static StringBuilder sb = new StringBuilder();


	// 소수인지 확인하는 메서드
	private static boolean isPrime(int n) {
		if (n == 1) return false;

		for (int i = 2; i * i <= n; i++) {
			if (n % i == 0) return false;
		}

		return true;

	}
	// end isPrime


	// 재귀
	private static void search(int idx, int n) {
		// 기저 조건
		// 인덱스가 N이 되면 끝
		if (idx == N) {
			sb.append(n + "\n");
			return;
		}

		// 짝수는 굳이 볼 필요가 없다.
		// 들어오는 n 을 String 으로 변경하여 끝에 1,3,5,9 을 붙이고
		// 소수인지 확인다.
		// 만약 소수라면 해당 숫자 다음 자릿수로 넘어간다.
		int nextNum = Integer.parseInt(Integer.toString(n) + 1);
		if (isPrime(nextNum)) search(idx + 1, nextNum);

		nextNum = Integer.parseInt(Integer.toString(n) + 3);
		if (isPrime(nextNum)) search(idx + 1, nextNum);

		nextNum = Integer.parseInt(Integer.toString(n) + 7);
		if (isPrime(nextNum)) search(idx + 1, nextNum);

		nextNum = Integer.parseInt(Integer.toString(n) + 9);
		if (isPrime(nextNum)) search(idx + 1, nextNum);

	}
	// end search


	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());

		// 첫번째 자리에 소수를 넣고 시작한다.
		search(1, 2);
		search(1, 3);
		search(1, 5);
		search(1, 7);

		// 출력
		System.out.println(sb.toString());

	}
	// end main
}

 

 

 

 

 

 

 

 

 

 

# 백준 신기한 소수 java # BJ2023 java

---