백준 1016 제곱 ㄴㄴ 수

x % s == 0 을 만족하는 제곱수 s가 존재 하지 않을때 x 를 "ㄴㄴ제곱수" 라고 한다.
문제의 수의 범위가 엄청나게 컸기때문에 처음부터 부르트 포스는 생각하지 않고 다른 방법을 생각하려고 헀다.

📜 문제 바로 가기 : 제곱 ㄴㄴ 수

제출코드

import sys
input = sys.stdin.readline

Min, Max = map(int, input().split())

# Min ~ Max 의 배열을 만들자.
arr = [True] *(Max - Min + 1)

def findNumber(n): # Min 이상의 값 중에 가장 작은 n 의 배수 구하기.
    a = Min // n
    if Min % n :
        b = 1
    else:
        b = 0
    return a + b

k = 2 # 제곱수의 제곱근
while k ** 2 <= Max: # Max 값보다 작은 제곱수만 보면 됨.
    square = k ** 2
    m = findNumber(square)
    while square * m <= Max:
        arr[square * m - Min] = False
        m += 1
    k += 1

print(sum(arr))

접근방법

Min ~ Max 의 True 배열을 만들어 놓고 제곱수의 배수는 False 로 바꾸는 방법을 이용했다.

우선 Min 값이 1조 까지 올 수 있기 때문에 배열에 인덱스를 숫자와 바로 매핑하기에는 무리가 있었지만, 다행이 Max 값이 최대 "Min + 백만" 이었기에 Min 값을 인덱스 0으로 매핑 시켰다.

그리고 2의 제곱 부터 시작해서 각 제곱수에 해당하는 인덱스를 False 처리했는데
Min 값이 1조 인데 4, 8, 16, 32 ... 이렇게 증가시키기엔 너무 이전 연산에서 낭비가 있다.
그래서 Min 값 이상의 숫자중 가장 작은 제곱수의 배수값을 찾아 불필요한 연산을 줄였다.

마지막으로 여기서 찾고자 하는 것은 "x % s == 0 을 만족하는 s값이 존재하는가?" 이기 때문에 s 가 Max 보다 큰 값은 볼 필요가 없다. 즉, Max 의 최대값 1조10만의 제곱근인 백만의 제곱까지만 보면 되겠다.