[Python/파이썬] 백준 1016번 제곱 ㄴㄴ 수

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

코드

from math import sqrt, floor

min_val, max_val = map(int, input().split())
length = max_val-min_val+1

non_square = [True]*length

for i in range(2, floor(sqrt(max_val))+1):
    square_num = i**2
    if min_val % square_num == 0:
        start = (min_val//square_num)*square_num
    else:
        start = (min_val//square_num+1)*square_num
    for j in range(start, min_val+length, square_num):
        non_square[j-min_val] = False

answer = 0
for i in range(min_val, max_val+1):
    if non_square[i-min_val]:
        answer += 1
print(answer)

 

에라토스테네스의 체를 조금 변형해서 풀 수 있었다.

문제를 보다보니 구간 내에 제곱 수로 나누어지지 않는 수가 몇 개인지 구하는 것이 에라토스테네스의 체를 사용하여 구간 내에 소수가 몇 개인지 구하는 것과 비슷하다고 생각하여 이렇게 풀었다.

 

다만 여기서 주의할 점은 min으로 주어지는 값의 범위가 1 ≤ min ≤ 1,000,000,000,000으로 매우 크다는 점이다. 그래서 소수인지 아닌지 판별한 결과를 저장하는 배열의 크기를 신경써줘야 했다. max까지 모든 결과를 저장하기 위한 배열을 만들면 메모리 초과가 발생한다.

 

그래서 딱 min과 max 사이의 판별 결과만을 저장하도록 non_square라는 배열을 생성하고, 2부터 max의 제곱근까지의 값들의 n배수들을 non_square에 False로 표시해두었다. 

 

최종적으로 만들어진 non_square에 저장된 값으로 min과 max 사이의 값들에 대해 이것이 제곱수로 나눠떨어지는 수인지 판별하면 된다. 이때 non_square는 min과 max 사이 구간의 길이만큼으로 만들어서 실제로는 i인 값의 판별 결과가 i-min에 저장되어있다고 보면 된다.