1016 - 제곱 ㄴㄴ 수
문제
어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다.
코드
a, b = map(int, input().split())
total = b - a + 1
check = [False] * (total + 1)
count = 0
idx = 2
while True:
val = idx ** 2
start = a // val
if val > b:
break
if a % val != 0:
start += 1
while start * val <= b:
if not check[start * val - a]:
check[start * val - a] = True
count += 1
start += 1
idx += 1
print(total - count)한마디
에라토스테네스의 체를 응용한 문제이다. min 과 max 사이에 있는 가장 작은 제곱수의 배수를 찾는다. 예를 들어 min이 11이면 가장 작은 제곱수의 배수는 12(4 X 3)이다.
그리고 해당 제곱수의 배수를 늘려가며 check 배열에서 지워주면 된다.
