백준 1456번 거의 소수

문제

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

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

문제풀이

사용한 알고리즘 : 에라토스테네스의 체

(0) 생각

 임의의 수 X 는 root(X)보다 큰 수로 나눠지지 않습니다.

 문제에서 입력되는 수는 10^14 이하의 수이므로 10^7 이하의 소수만 찾아줄 것입니다.

 찾은 모든 소수를 거듭제곱 해보면서 A 이상 B 이하의 범위에 들어가는지 체크해줍니다.

(1) 코드 12~17

 10^7 이하의 소수를 모두 구해 저장합니다.

(2) 코드 21~29

 구해 놓은 모든 소수를 거듭제곱 해보면서 A이상 B이하의 범위에 들어가는 경우 수를 구해줍니다.

(3) 주의

 소수의 N제곱(N>=2) 입니다. 소수의 1제곱 (자기자신)은 세주면 안됩니다.

 구현을 하면서 숫자가 매우 커져서 long long 의 범위를 넘어갈 수 있습니다. 주의해주세요.