백준 번 2023번 : 신기한 소수 자바

 

 

 

🧫 문제 분석

 

✔️ 출처

신기한 소수 골드 5

 

📖 문제

 

 

(첫번째 수 + 두번째 수) 가 소수면 

첫번째 수 * 10 + 두번째 수 를 파라미터로 넘겨 재귀로 호출한다. 

 

백트래킹으로 풀어주면 된다. 

소수 판별은 제곱근을 이용한 방법을 사용했다. 

 

판별할 수의 제곱근을 구해서

2~제곱근까지의 수로 나눠떨어지면 소수가 아니다.

 

자세히 말하자면

 

n = p*q 라 했을 때 (n > 0)

 

p >=√n 일때

p로 나누면 그 몫은 q이며

q <= √n 이다.

한쪽이 √N이상이고, 한쪽이 √N이하인 수의 곱이다. 

 

4를 생각해보자

p x q	√N = 2      p            q
1 x 4	1  ≤ √N,  4  ≥ √N
2 x 2	2  ≤ √N,  2  ≥ √N
4 x 1	4  ≥ √N,  1 ≤  √N

1은 소수가 아니지만 여기선 예를 들어 설명하면

1 x 4 = 4 x 1 이고

결국에는 1로 나누어 떨어진다. 

따라서 굳이 4를 4로 나눠볼 필요없이 1로 나눠보면 알 수 있다.

 

 

따라서 2 ~ √N 이하의 수로 나눠보면 소수인지 아닌지 알 수 있다.

 

 

---

🔅 문제 풀이

import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());

        recursion(0, 0);


        bw.write(sb.toString());
        bw.flush();
        bw.close();

    }


    private static void recursion(int depth,int prime) {
        if (depth == n) {
            sb.append(prime).append("\n");
            return;
        }


        for (int i = 0; i < 10; i++) {
            if (isPrime(prime + i)) {
                recursion(depth + 1,
                        depth +1 != n ? (prime + i) * 10 : (prime + i));
            }
        }
    }

    private static boolean isPrime(int num) {
        if (num < 2) return false;

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

        return true;
    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.  오랜만에 소수판별 문제를 푸니 약간 헷갈렸다. 이번기회에 다시 상기시켰다.