백준 1016번 제곱ㄴㄴ수 - Python 프로그래밍

[@WonsTV1234]

파이썬 코드(설명 포함) import math #sqrt 함수를 사용하기 위해서 시작하기 mn, mx = map(int, input().split()) #입력 받기 max_sqrt = int(math.sqrt(mx)) + 1 #제곱수의 조사 범위 찾기 squares = [ i**2 for i in range(2, max_sqrt+1) ] #2 이상 max_sqrt 이하의 제곱수 리스트 작성하기 ranges = mx - mn + 1 #범위 안의 수의 개수 찾기 L = [ 1 for _ in range(ranges)] #제곱ㄴㄴ수를 체킹할 리스트 만들기 for i in squares: #에라토스테네스의 체와 같은 방식으로 제곱수의 배수를 제거하기 위해 제곱수 리스트 squares의 원소를 하나씩 꺼내기 j = int(min(mn/i, (mn//i)+1)) #i에 곱할 수 j의 최솟값(min보다 큰) if i*j>mx: break #j의 최솟값이 mx보다 크면 리스트 인덱스 오류가 나므로 멈추기 while True: if i*j-mn >= 0 and i*j-mn < ranges: #위와 같은 인덱스 오류 방지하기 L[i*j - mn] = 0 #제곱수 i의 배수 제거하기 j += 1 #제곱수 i에 곱하는 상수 j를 증가시키기 if i*j > mx: break print(sum(L)) #값이 1(True)인 원소, 즉 제곱 ㄴㄴ수의 개수 출력하기