거의 소수

• 풀이 자체는 간단하다. 소수의 리스트 p_i를 구한다음, 각 p_i에 대해서 A ≤ p_i^x ≤ B 이고 x≥2인 x의 갯수를 구해서 모두 더하면 된다.
• 소수 목록은 최대 sqrt(B) 까지만 구하면 된다.
• 개인적으로 고생하다가 실패했던 부분은 A ≤ p_i^x ≤ B 인 x의 갯수를 구하는 것을 로그함수를 이용해서 구하려 한것. int(log(B,p_i)) - int(log(A-1, p_i)) 로 계산하는 것은 수학적으로는 문제없는 풀이이다. 그러나 실수 오차로 인해서 math.log의 결과가 부정확한 경우가 생긴다. 예를 들면 math.log(243, 3) 의 결과는 5.0이 아닌 4.99999999가 되고 따라서 int를 씌우면 4가 되어서 오답이 나온다.
• 쉽게 푸는 방법은 로그를 사용하는 것이 아니라, 다소 무식하게 값이 B보다 커질때까지 p_i를 반복해서 곱해가면서 갯수를 세는 방법이다.
  • 조금 더 기교를 부리면 이분탐색으로 찾을수도 있다.
• 시간복잡도는 좀 헷갈린다. 우선 에라토스테네스의 체를 이용해서 소수 목록을 구하는 데에 O(sqrt(B)*loglogB)이 걸린다. 이렇게 찾은 소수의 갯수는 O(sqrt(B)/logB)일거고, 각각에 대해서 B보다 커질때까지 곱해나가면 최대 O(logB) 번 곱하게 될것이니까.. 이 과정은 O(sqrt(B))라고 할수 있을것 같다. 그러면 총 시간 복잡도는 O(sqrt(B)loglogB).
• python의 Decimal을 사용해서 유효자릿수를 충분히 크게 고정시키면 로그 방식으로 실수오차 없이 값을 구할수 있기는 하다. 그러나 이경우는 시간 초과가 발생한다 ㅜ

"""Solution code for "BOJ 1456. 거의 소수".

- Problem link: https://www.acmicpc.net/problem/1456
- Solution link: http://www.teferi.net/ps/problems/boj/1456
"""

from teflib import numtheory


def main():
    A, B = [int(x) for x in input().split()]
    primes = numtheory.prime_list(int(B**0.5))
    answer = 0
    for p in primes:
        t = p * p
        while t < A:
            t *= p
        while t <= B:
            answer += 1
            t *= p

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.numtheory.prime_list