(Python) 백준 1016 - 제곱 ㄴㄴ 수

https://www.acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

 

아이디어

- 특정 구간 내 모든 소수들을 효율적으로 구하기 위해서 에라토스테네스의 체를 사용

- 입력 값이 매우 크기 때문에 1부터 최대값이 아닌 최소값부터 최대값만 계산

 

 

 

코드

#입력
n,m=map(int,input().split())

#에라토스테네스의 체 생성 시 1이 아닌 최소값부터 시작
a=[1]*(m-n+1)

for i in range(2,int(m**.5)+1):
    k=i**2 # 제곱수
    
    # n 이하의 k의 배수 중 최댓값에서 시작
    for j in range(n//k*k, m+1, k):
    	
        # j는 최소값보다 작을 수 있으므로 체크해야 함
        if j-n>=0 and a[j-n]: a[j-n]=0

#남아있는 1의 개수 = 제곱ㄴㄴ수의 갯수
print(sum(a))