BOJ_1456 : 거의 소수

👉 문제링크

1456번: 거의 소수

---

---

🔸 문제 분석 🔸

• 어떤 소수의 N제곱 (N>2)의 수를 거의 소수라고 한다.
• A이상 B이하의 거의 소수의 개수를 출력한다. (1<=A<=B<=10^14)

🔸 문제 풀이 🔸

• 10^14 까지의 수에서 거의 소수를 찾으려면, 그 제곱근인 10^7까지의 소수를 찾아야 한다.
  • 10^7의 제곱이 10^14이므로, 적어도 10^7까지는 소수를 찾아야 N제곱 계산을 할 수 있다.
• 10^7까지의 소수는 에라토스테네스의 체로 구한다.
• 구한 각각의 소수에서 N제곱한 값이 B보다 커질 때까지 반복한다. 그 중 A보다 크거나 같은 경우를 카운트한다.
  • N제곱의 값이 long형을 초과할 수 있으므로 이항 정리로 해결한다
  • N^k <= B  ====> N <= B / N^(k-1)

🔸 코드 🔸

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

public class Main {
    public static void main(String[] args) throws IOException {
        final int MAX = 10_000_001;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());
        boolean[] pn = new boolean[MAX];

        for (int i = 2; i <= Math.sqrt(MAX); i++) {
            if (!pn[i]) {
                int mul = 2;
                while (i * mul < MAX) {
                    pn[i * mul++] = true;
                }
            }
        }

        int cnt = 0;
        for (int i = 2; i < MAX; i++) {
            if (!pn[i]) {
                long n = i;
                while ((double) i <= (double) B / (double) n) {
                    if ((double) i >= (double) A / (double) n) {
                        cnt++;
                    }
                    n *= i;
                }
            }
        }

        bw.write(Integer.toString(cnt));
        bw.flush();
    }
}

🔸 코드 해석 🔸

• 에라토스테네스의 체로 소수를 구하기 위해 boolean 배열 pn을 만들어 10^7의 제곱근까지 소수를 구한다.
• 각 소수의 N제곱 결과가 A~B인 경우를 카운트한다.
  • N제곱 결과에서 long형을 넘을 수 있으므로 이항 정리를 통해 비교한다.
• 카운트를 출력한다.

---

🔸 end 🔸

• 에라토스테네스의 체는 익숙한데, 이항 정리에 대한 아이디어가 생소했던 문제였다.
  • long형을 넘는다는 계산이 예상하기 힘들었다.