문제 링크

<aside> 💡 수학/정수론/소수 판정/에라토스테네스의 체

</aside>

Memory 38724KB Time 1480ms Code Length 322B

min, max = map(int, input().split())
validate = [1 for i in range(max-min+1)]
cnt=0
i=2
while i**2 <= max:
    mul = min // i**2
    while mul * (i**2) <= max:
        if mul * (i**2) - min >= 0 and mul * (i**2) - min <= max-min:
            validate[mul * (i**2) - min] = 0
        mul +=1
    i +=1

print(sum(validate))

이 코드는 사용자로부터 두 개의 정수를 입력받아 이 두 수 사이에 있는 완전 제곱수가 아닌 수의 개수를 찾는 것이다.

먼저, min과 max 사이의 모든 수를 포함하는 리스트 validate를 생성하고, 모든 요소를 1로 초기화한다. 이후, 2부터 시작하여 max의 제곱근까지의 모든 수에 대해, min과 max 사이의 모든 배수를 찾아 해당 인덱스의 validate 값을 0으로 바꾼다.

이렇게 하면, validate 리스트의 각 인덱스는 min과 max 사이의 해당 숫자가 완전 제곱수인지 아닌지를 나타낸다. (완전 제곱수는 0, 아니면 1)

마지막으로, validate 리스트의 모든 요소를 합하여 완전 제곱수가 아닌 수의 개수를 출력한다.