[baekjoon] 1016 제곱ㄴㄴ수(python)

min과 max를 입력받아 min부터 max까지의 수 중에 어떤 수의 제곱수의 배수가 아닌 수(=제곱ㄴㄴ수)의 갯수를 찾으면 되는 문제이다.
알고리즘 분류에 "에라토스테네스의 체"라고 되어있길래 한 번 찾아봤다.

에라토스테네스의 체

소수를 찾는 빠르고 쉬운 방법이다.
방법은 예시와 함께 설명하겠다.
최대값:120

1. 제곱했을 때 최대값을 넘는 가장 작은 수의 -1을 구한다. (ex: 제곱해서 최대값을 넘는 가장 작은수:11, 11 - 1 = 10)
2. 2부터 시작해 10까지 모두 돌며 1~120까지 도는데 나누어 떨어지는 수는 지운다.
3. 남은 숫자들은 모두 소수이다.

위의 방법을 사용하여 제곱ㄴㄴ수를 구하는 방법을 생각해보았다.
우선 나는 에라토스테네스의 체 처럼 전체 범위의 갯수를 만들고 배수들을 지우는 방식으로 결정했다.
min부터 max까지 갯수의 리스트를 만들고 True로 모두 채운다.
예를 들어 min이 20이고 max가 22이면
lst[0]은 20을 가리키고 lst[1]은 21을 가리킨다.

cnt = max - min + 1
lst = [True] * (max - min + 1)

2부터 시작해 제곱했을 때 최대값을 넘는 가장 작은 수를 구하는 것 까진 같은데
그 수들의 제곱이 나눠지는지 확인해야하므로 제곱을 해서
탐색한다.

for i in range(2, int(max**0.5 + 1)):
    square = i**2

탐색 횟수, 시간을 최대한 줄이기 위해 min부터 max까지 모두 돌기보단, min이상 가장 작은 square의 배수를 찾고, max까지 square만큼 키우면서 제외해준다. (이미 작은 수의 배수로 결정된 수는 False로 바뀌어있으므로 if문으로 걸러 조금이라도 시간을 아껴준다)

    for j in range((((min - 1) // square) + 1) * square, max+1, square):
        if lst[j - min] == True:
            lst[j - min] = False
            cnt -= 1

min 이상 가장 작은 square의 배수를 찾는 공식이 (((min-1)//square)+1)square인 이유는 예시를들면 간단하다.
min을 19으로 잡고 max를 32로 넉넉잡고 square를 4라고 한다면, ((18//4)+1)4를 해주면 20이 나오게 된다. (다른 예시를 여러가지 넣어보면서 왜 저렇게 되어야하는지 확인해보는 것도 좋을 것 같다)

전체 코드는 다음과 같다.

import sys
input = sys.stdin.readline
min, max = map(int, input().strip().split())
cnt = max - min + 1
lst = [True] * (max - min + 1)
print(max ** 0.5)
for i in range(2, int(max**0.5 + 1)):
    square = i**2
    for j in range((((min - 1) // square) + 1) * square, max+1, square):
        if lst[j - min] == True:
            lst[j - min] = False
            cnt -= 1
print(cnt)

아직 알고리즘이 익숙치않아 자신이 없어서 골드1 문제길래 쫄았는데 생각보다 에라토스테네스의 체를 활용하면 간단한 문제였다.