Aidengoldkr – Tech Blog

제곱 ㄴㄴ 수 - 골드 1

문제

어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

입력

첫째 줄에 두 정수 min과 max가 주어진다.

출력

첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다.

제한

1 ≤ min ≤ 1,000,000,000,000

min ≤ max ≤ min + 1,000,000

이 문제는 소수판별 문제가 비슷한 계열의 문제이다. 일단 제한부분을 못면 브루트포스 탐색 방식 절대 불가능한 문제임을 알 수 있다. 에라토스테네스 체 공식을 응용하여 소수 대신 제곱수의 배수를 판별해내는 방식으로 풀이하였다.

풀이코드

import math

min_, max_ = map(int,input().split())
size = max_ - min_ + 1
is_nono = [True] * size

l = int(math.isqrt(max_))

for i in range(2,l+1):
    s = i*i
    start = ((min_ + s - 1) // s) * s
    for j in range(start, max_ + 1, s):
        is_nono[j - min_] = False

print(sum(is_nono))

허용치인 1 부터 1조까지 리스트를 구성 할 수 없으니, 입력 받은 max와 min을 기반으로 size 변수를 만들고 size 수 만큼 True로 채워 놓은 is_nono 라는 불리언 리스트를 만들었다.

이후 L 변수에 탐색할 제곱수의 최대값을 저장하고 (max의 음수가 아닌 정수 제곱근) 2부터 L+1 까지 반복하며 제곱수 (4,9,16,.....L+1xL+1)를 s에 저장한다.

start를 통해 min 이상인 가장 작은 제곱수 배수의 몫에 다시한번 제곱수 배수를 곱하여 유효범위 내 최소의 제곱수 배수를 구한다.

이후 최소 제곱수 배수부터 최대치까지 제곱수 배수를 is_nono에서 False로 전환하고 is_nono에 남아있는 True 값의 수를 출력한다.