1456 거의 소수

어떤 자연수가 소수의 N제곱 꼴일 때 거의 소수라고 한다. 이 떄 a부터 b까지 거의 소수의 개수를 구하는 문제이다.

범위가 10^14 까지 되지만, N제곱(N>1)이기 때문에 10^7까지의 소수만 나타나게 된다. 따라서 에라토스테네스의 체로 10^7까지 소수를 걸러주고, 그 소수들에 대해 계속 거듭제곱을 하면서 a와 b사이에 들어있는지 판별하면 된다.

p.s. long long 형으로 구현을 해주니 overflow 문제가 발생했다. 이것저것 고쳐보려다 안되서 double 형을 사용하니 해결이 되었다.

소스