[백준, BOJ] 1016 - 제곱ㄴㄴ수

1. Question

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

1.1 Input

첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000,000보다 작거나 같은 자연수이다.

1.2 Output

첫째 줄에 [min,max]구간에 제곱ㄴㄴ수가 몇 개인지 출력한다.

1.3 Example

입력	출력
1 10	7

2. Approach

기본적인 아이디어는 에라토스테네스의 체를 이용한 소수 얻기와 같다. 이 문제에서는 소수가 아니라, 제곱수로 나눠나간다는 것을 주의하면 된다.

처음에는 제곱수로 나뉘는지를 저장하는 nonoList가 boolean list니까 sum(nonoList)를 출력하니 수행시간이 2.5초가 나왔다.

그래서 sum의 문제인지를 판별하기 위해, False로 갱신할 때 마다 카운트를 하고 len(nonoList) - cnt를 하니 1.6초로 줄어들었다. 나름 기억해둘 만한 내용인 듯.

3. Submission

4. Code

MIN, MAX = map(int, input().split())

nonoList = [True] * (MAX - MIN + 1)

i = 1
cnt = 0
while i*i <= MAX:
    i += 1
    t = MIN // (i**2)
    if MIN % (i**2):
        t += 1
    num_t = t * (i**2)
    while num_t <= MAX:
        if nonoList[num_t - MIN]:
            cnt +=1
            nonoList[num_t - MIN] = False
        num_t += (i**2)

print(len(nonoList) - cnt)