[백준] 1016번 - 제곱ㄴㄴ수

문제 링크 : 

 

문제

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

 

입력

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

 

출력

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

 

풀이

import math

A, B = map(int, input().split())
num = [False for _ in range(A,B+1)]
count = 0

for b in range(2,int(math.sqrt(B))+1):
    k = b*b
    start = max(A, ((A+k-1)//k)*k)
    for j in range(start,B+1,k):
        if not num[j-A]:
            if A <= j:
                count+=1
                num[j-A] = True
            
print(B-A+1-count)

 

해설

• 에라토스테네스의 체를 응용하여 풀었다.
• 처음엔 j를 설정하는 반복문의 start를 2로 설정하려했으나 런타임에러(IndexError)가 발생하였다. j-A가 B-A보다 클 수도 있어서 발생한 오류였다.
• 그래서 start를 A이상으로 설정하여 에러를 방지하였다.
  • ((A+k-1)//k)*k) 는 A 이상 숫자 중 가장 작은 k의 배수를 말한다.