1016. 제곱 ㄴㄴ 수 (Python)

1016번: 제곱 ㄴㄴ 수

 

풀이

 에라토스테네스의 체를 활용하여 문제를 해결할 수 있다. 일단 입력으로 주어진 두 수 사이에 있는 수의 개수만큼 크기를 가진 배열을 만든다. 예를 들어 51과 100이 입력으로 주어졌다면 총 50개의 숫자가 있기 때문에 50의 크기를 가지는 배열을 만들어준다. 이때 51 ~ 100에 해당하는 임의의 숫자 n은 해당 배열의 n - 51번째 인덱스에 해당한다. 즉, 임의의 숫자 n에서 입력으로 주어진 min값을 빼주면 해당 배열에 접근할 수 있다.

 

 제곱수는 2의 제곱부터 시작하여 입력으로 주어진 max 값의 제곱근까지 탐색하면 된다. min ~ max 사이에서 제곱수의 배수가 어디부터 어디까지 해당하는지를 구하고 해당 범위에서 위에 만들어준 배열의 값을 바꾸어 해당 숫자가 제곱수의 배수임을 체크하면 된다. 

 

코드

from math import sqrt

if __name__ == '__main__':
    a, b = map(int, input().split()) # a: 최솟값, b: 최댓값
    res = b - a + 1 # a ~ b 범위의 숫자 개수

    nums = [True for _ in range(res)] # res만큼의 크기를 가진 배열을 만들어준다.

    # 제곱수는 2의 제곱부터 시작하여 최댓값의 제곱근까지의 제곱수까지 탐색한다. 
    for i in range(2, int(sqrt(b)) + 1):
        square = i ** 2 # 숫자 i의 제곱수 
        start = a // square
        if a % (i*i) != 0:
            start += 1

        end = b // (i*i)

        start, end = square * start, square * end # a ~ b 범위에 대하여 square의 배수가 start부터 시작하여 end까지 존재한다. 
        
        # start부터 end까지 square의 배수를 찾아서 False로 값을 바꾼다.
        for j in range(start, end+1, square):
            # nums 배열의 인덱스는 0부터 시작하는데 숫자 j의 인덱스는 j에서 입력으로 주어진 최솟값을 빼면 구할 수 있다.
            # 이미 제곱수의 배수로 체크된 숫자는 건너뛴다.
            if not nums[j - a]:
                continue
            
            # 아직 체크되지 않은 정수라면 False로 체크해주고 숫자의 개수를 1나 감소시킨다.
            nums[j - a] = False
            res -= 1

    print(res)