[백준✨] 1106번 <제곱ㄴㄴ수> / Python 문제풀이

해답)

import sys
import math

def input():
    return sys.stdin.readline().rstrip()

MIN, MAX = map(int, input().split())
last = int(math.floor(math.sqrt(MAX))) # 마지막 후보 제곱수, MAX보다 작은 last*last  

'''
MIN 부터 MAX까지 아리스토 체를 구현한다.
res[0] == res[MIN]
이걸 의미하게 하기 위해
넣어줄 떄 res[n-MIN] 을 해준다. 
'''
res = [True for i in range(MAX-MIN+1)] 

for i in range(2, last+1):
    zegop = i * i
    mok = MIN // zegop # 몫을 1씩 높여주며 걸러준다.
    while True:
        nxt = mok * zegop # 걸러질 수 (제곱수의 합성수)
        if nxt < MIN:
            mok += 1
            continue
        if nxt > MAX:
            break 
        res[nxt - MIN] = False
        mok += 1
       
cnt = 0
for r in res:
    if r:
        cnt+= 1       
 
print(cnt)

---

풀이)

1. 이렇게 문제 길이가 짧고, 이해가 간단한 문제일수록 읽을 때 반드시 입력 범위를 확인한다.

2. 입력 범위가 1,000,000,000,000보다 작거나 같은 자연수 이고, MIN~MAX 범위는 최대 백만이므로 , 하나하나 테스트하는 거는 절대 시간상 될 수 없다.

   => 따라서! 아리스토테네스 체의 방식을 도입한다.

   * 여기서 체의 인덱스는 MIN에서부터 MAX까지로 하면 배열의 메모리 초과가나므로, MIN 을 0으로 생각하는 리스트       를 이용한다.

3. 2*2 부터 3*3 .... k*k 까지 루프를 돌며, 배수들을 체에서 걸러내준다.

   이 때, k*k 는 MAX보다 작으면서 가장 큰 k 이다!

4. 체에서 걸러지지 않은 수들의 개수를 출력한다.

 

 

 

 

* 위 문제의 저작권은 백준(https://www.acmicpc.net/) 에 있습니다.