(Java/자바) - 백준(BOJ) 2023번 : 신기한 소수

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

2023번: 신기한 소수

---

• 문제 : 

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

 

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

 

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

 

 

 

---

• 풀이 :

백트래킹 문제였습니다. 

 

풀이는 다음과 같습니다.

 

1. 백트래킹 함수인 Solution을 선언합니다. 이 때, 파라매터는 현재 확인할 값, 자릿수 총 2개입니다.

 

2. 1부터 9까지 모든 자릿수에 대해 한 자릿수씩 확장하며 재귀호출을 실행합니다.

 

3. 각 확장마다 isPrime 함수를 실행하여 해당 수가 소수가 아닐 경우 더이상 실행하지 않습니다.

 

4. 소수판별 알고리즘의 효율성을 위해 범위를 n까지가 아닌 루트n까지로 하였습니다.

(약수의 중간값을 찾아서 이 값까지 나눠지는 수가 없다면 더이상 확인할 필요가 없습니다.)

참고 : https://myjamong.tistory.com/139

소수(Prime Number) 구하기 효율적 알고리즘 :: 코드자몽

 

5. 자릿수가 N이 된다면 이 수가 소수인지 판단하고 소수라면 출력합니다.

 

 

 

 

 

 

---

• 소스코드 : 

import java.util.Scanner;

public class Main{
	static int N;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		Solution(0, 0);
		System.out.println(sb.toString());
		
	}
	public static void Solution(int n, int cnt) {
		if (cnt == N) {
			if (isPrime(n)) sb.append(n).append("\n");
			return;
		}
		if(!isPrime(n)) return;
		for (int i = 1; i < 10; i++) {
			Solution(n*10 + i, cnt+1);
		}
		
	}
	public static boolean isPrime(int x) {
		if (x == 1) return false;
		for (int i = 2; i < Math.pow(x,0.5); i++) {
			if (x % i == 0) return false;
		}
		return true;
	}
	
	
}