[Java Algorithm] 신기한 소수 BOJ #2023

문제

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

2023번: 신기한 소수

 

내 문제 풀이

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Scanner;

public class BOJ_2023 {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Deque<Integer> que = new ArrayDeque<>(Arrays.asList(2, 3, 5, 7));
		int[] secondNums = {1, 3, 7, 9};
		boolean isFirst = true;
		int[] toPlus = new int[n];
		toPlus[0] = 1;
		for(int i = 1; i < n; i++) toPlus[i] = toPlus[i-1] * 10;
		int idx = 0;
		
		mainLoop:
		while(true) {
			int num = que.removeFirst();
			
			if(idx >= 4) {
				for(int i = 2; i <= Math.sqrt(num); i++) {
					if(num % i == 0) continue mainLoop;
				}
			}
			
			for(int i: secondNums) {
				String tmp = Integer.toString(num);
				if(tmp.length() == n) {
					que.addFirst(num);
					break mainLoop;
				}
	
				que.add(i + (num * 10)); // 자릿수 늘려주며 수 더하기
			}
			
			if(idx <= 4) idx++;
		}
		
		printLoop:
		while(que.size() > 0) {
			int num = que.removeFirst();
			for(int i = 2; i <= Math.sqrt(num); i++) {
				if(num % i == 0) continue printLoop;
			}
			System.out.println(num);
		}
	}
}

👉 구현 문제 !

이 문제는 무엇보다 소수 판별과 '신기한 소수'의 규칙을 찾아내는 것이 중요한 것 같다.

 

[ '신기한 소수'의 규칙 ]

1. 신기한 소수의 경우 첫 번째 글자는 꼭 소수여야만 한다.
   -> 2, 3, 5, 7 네 숫자만이 첫 번째 자리에 올 수 있다.
2. 신기한 소수의 두 번째 글자부터는 꼭 홀수이며 5가 아니어야 한다.
   -> 1, 3, 7, 9 네 숫자만이 두 번째 이상의 자리에 올 수 있다.

[ 소수 판별법 ]

소수는 1과 자기자신으로만 나누어 떨어지는 수를 말한다.
따라서 2부터 자기 자신의 전까지 나누어 볼 수 있겠지만,

자기 자신까지 비교해볼 필요 없이, 제곱근까지만 나누어도 확인이 가능하다.

 

💡 피드백

• 소수 판별법만 잘 알고 있다면 쉽게 풀 수 있는 문제였다.