[BOJ] 1016번 제곱 ㄴㄴ 수 (Python) [Do it!]

문제

https://www.acmicpc.net/problem/1016

풀이

문제를 보면 min과 max 사이 텀이 최대 1,000,000인 것을 보고 이 구간을 선형 탐색하면 문제가 없다고 생각했고, 에라토스테네스의 체도 생각했다.

다만, 가능한 제곱수가 2^2부터 (10^6)^2 까지 가능하여, 얕은 생각으로 10^6 * 10^6 이 되어 에라토스테네스의 체는 어렵겠다고 생각하고, 고민하다가 풀이를 봤는데, 에라토스테네스의 체를 이용하는 것이었다.

생각해보면, min, max 사이 구간에 해당하는 10^6은 그대로 시간복잡도에 곱해지지 않는다.

따라서 에라토스테네스의 체로 코드를 작성했고, AC처리됐다.
이때, 처음 시작하는 부분인 start = (min_n//sqr_num)*sqr_num 의 작성이 조금 어려웠으나, 추후에는 빠르게 작성할 수 있을 것 같다.

또한, 이 문제의 시간복잡도를 어떻게 작성해야 할지 모르겠는데, 고민을 해봐야겠다.

from collections import defaultdict
from math import sqrt

min_n, max_n = map(int, input().split())

default_dict = defaultdict(int)  # 1이면 나눠떨어짐

check_num = 2
while (check_num <= sqrt(max_n)):
    sqr_num = check_num**2
    start = (min_n//sqr_num)*sqr_num
    while start <= max_n:
        default_dict[start] = 1  # 나눠떨어짐
        start += sqr_num
    
    check_num += 1

# 에라토스테네스에서 걸러진거 제외시키기
ans = max_n-min_n+1
for num in range(min_n, max_n+1):
    if num in default_dict:
        ans -= 1

print(ans)