[BOJ][🟡1][백준#01016] 제곱 ㄴㄴ 수

문제 출처

BAEKJOON Online Judge #1016

문제

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

입력

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

출력

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

제한

1 ≤ min ≤ 1,000,000,000,000 min ≤ max ≤ min + 1,000,000

예제

예제 1

입력

1 10

출력

7

예제 2

입력

15 15

출력

1

예제 3

입력

1 1000

출력

608

My Sol

mn, mx = map(int, input().split())
check = [1]*(mx-mn+1)

sqr_n = 2
while sqr_n**2 <= mx:
    sqr_nn = sqr_n**2
    k = (mx//sqr_nn)*sqr_nn
    while k >=mn:
        check[k-mn] = 0
        k -= sqr_nn
    sqr_n += 1

print(sum(check))

1. 에라토스테네의 체를 적용하기 위해 제곱 ㄴㄴ 수를 0으로 체크할 배열 check 를 만든다.
2. 제곱수의 시작을 2의 제곱부터 하여 1씩 늘려가며 제곱수로 나누어 떨어지는 수들을 0으로 체크해준다.
3. 이 반복은 제곱수의 값이 mx를 넘어서는 순간까지 진행한다.
4. 최댓값(mx)을 제곱수(sqr_nn)로 나눈 몫을 제곱수로 다시 곱한다. 이는 mx를 넘지 않는 가장 큰 제곱ㅇㅇ수 이다. 이 수부터 제곱수 sqr_nn간격으로 k를 낮춰준다.
5. 이 반복은 k가 mn 미만으로 떨어질 때까지 반복한다.
6. 이렇게 check 배열을 에라토스테네스의 체 개념으로 걸러내주면, check에는 제곱 ㄴㄴ 수만 1로 체크가 된다.
7. 이를 모두 더한 값을 출력한다.

결과

맞았습니다!!