[백준 01456] 거의 소수 [Java]

문제

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

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

입력

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

출력

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

1456번: 거의 소수

---

 

풀이

A와 B사이의 수 중 소수의 N제곱에 해당하는 "거의 소수"의 갯수를 구하는 문제다.

거의 소수는 최소 p^2이므로, A와 B에 대해 2 ~ sqrt(B)사이의 소수를 제곱해보며 유요한 수를 찾으면 된다.

우선, B <= 10^14이므로, 10^7까지의 수들에 대해 어떤 수가 소수인지 알아야 한다.

Sieve of EratosThenes를 이용해 소수들을 구해주자.

이제 2부터 sqrt(B)까지의 소수들에 대해 제곱수가 범위에 해당하는지 확인해야 한다.

이때, 오버플로우가 발생할 수 있다.

거의 소수에 i를 제곱하지 말고 B에 i를 나누어 안전하게 계산하자.

---

소스코드

보기