BOJ 2023번: 신기한 소수

문제

문제 바로가기> BOJ 2023번: 신기한 소수

2023번: 신기한 소수

 

풀이

왼쪽 부터 자리 수를 늘려가면서 소수인지 판정한다.

cnt == N , 즉 N 자리가 되기전에, 소수가 아니라고 판별되면, 그 이후로는 더 볼 필요가 없다!

 

첫 째 자리 수가 소수일 수 있는 경우는 `2, 3, 5, 7` 뿐이고,

둘 째 자리부터 짝수로 끝나는 경우는, 소수가 될 수 없다.

 

소수를 판별할 때는 N의 제곱근 까지만으로 나누어 보면 된다!

 

💡 소수 판별 시 N의 제곱근 까지만 나누어 보면 되는 이유
   
✔️ 합성수 n은 자연수 a, b에 대해 n = a * b 로 나타낼 수 있음 (a, b는 자연수)
✔️ m = sqrt(n)이라고 가정하면,  n = m * m 이라고 할 수 있음
✔️ n = a*b이고, n = m*m 이라 했으므로 a*b = m*m 

→ a와 b가 자연수가 되려면 다음의 세가지 경우 중 하나만 가능함
1. a=m 이고 b=m
2. a<m 이고 b>m
3. a>m 이고 b<m

따라서, min(a, b) <= m 

✔️ 즉, n의 모든 약수에 해당하는 a와 b가 어떠한 약수이더라도
둘 중 하나는 무조건 m(=sqrt(n)) 이하 이므로, m까지만 조사한다면 n이 소수인지 알 수 있음

 

import java.io.*;

public class Main {
	
	static StringBuilder sb = new StringBuilder();
	
	static int N;
	static int SingleDigitPrime[] = {2, 3, 5, 7};
	
	public static void main(String[] args) throws Exception {
		// System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = br.read()-'0'; // 1 ≤ N ≤ 8 (char to int)
		
		for(int start : SingleDigitPrime) solution(1, start);
		System.out.println(sb.toString());
	}

	static void solution(int cnt, int num) {
		if(!isPrime(num)) return; // 소수가 아닌 경우 
		if(cnt == N) {
			sb.append(num).append("\n"); // N자리 신기한 소수
			return ;
		}
		for(int i=1; i<10; i+=2) { // 짝수로 끝나면 소수가 될 수 없음 (오름차순으로 정렬해서 한 줄에 하나씩 출력)
			solution(cnt+1, num*10+i);
		}
	}

	static boolean isPrime(int num) { // 소수 판별
		for(int i=2; i*i<=num; i++) {	
			if(num%i == 0) return false;
		} return true;
	}
}