[BOJ 1456] 거의 소수

문제 링크 : https://www.acmicpc.net/problem/1456

본문

어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.

두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

입력

첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다.

출력

첫째 줄에 총 몇 개가 있는지 출력한다.

제한

시간 제한	메모리 제한
2sec	256MB

• 1 ≤ A ≤ B ≤ 10¹⁴

---

풀이

우선 소수들을 모두 찾아놓아야할 것 같다. 미리 찾아놓아야하는 소수의 범위는 $1$부터 $10^7$까지이다. $B$의 최댓값이 $10^{14}$이므로 이 범위 내에서 거의 소수를 만들 수 있는 소수의 최댓값은 $\max \sqrt{B} = 10^7$이기 때문이다. 이 정도는 소수판별법 :: 에라토스테네스의 체로 찾아놓을 수 있을 것 같다. 그 다음, 찾은 모든 소수에 대해 그 소수로 만들 수 있는 거의 소수의 개수를 세면 된다. 어떤 거의 소수 $x$는 그 표현법이 항상 유일하므로, 소수들을 찾아냈다면 그 수들을 계속해서 제곱해나가며 거의 소수의 개수를 세면 된다. 구현 자체는 매우 간단해보인다.

대신, 이 문제에는 함정이 하나 있다. 찾은 소수 $a$가 대략 $10^7$ 정도라면, $a^2 \approx 10^{14}$지만 $a^3 \approx 10^{21}$이다. long long의 범위가 대략 $10^{19}$ 정도이므로 이 경우에는 오버플로가 발생한다. 제곱해나갈 때 오버플로가 발생하는 부분에 대한 핸들링이 추가로 필요하다는 것. 현재는 세제곱이 문제이므로, 세제곱을 하더라도 오버플로가 발생하지 않는 지점을 생각해보자. 나는 여기서 $10^6$을 선택했다. $a < 10^6$과 $a > 10^6$인 경우로 나눠서 생각해보자.

• $a < 10^6$인 경우 :: $a^2 < 10^{12}$, $a^3 < 10^{18}$이다. 이 경우 오버플로가 발생하지 않으며 $a^3 > \max B$이므로 구현에 지장이 없다
• $10^ 6 < a < 10^7$인 경우 :: $10^{12} < a^2 < 10^{14}$, $10^{18} < a^3 < 10^{21}$이다. $a^3$이 이미 $\max B$의 범위를 넘었으므로 이 범위 내의 $a$는 세제곱할 필요가 없다!

즉, 이 문제에서는 우선 범위 내의 모든 소수를 탐색한 후, 오버플로가 발생하지 않는 기준을 두고 거의 소수를 찾는 과정을 진행하면 된다.

소스코드

Github Link : Source Code

참고 알고리즘 : 소수판별법 :: 에라토스테네스의 체