문제

[백준] 제곱 ㄴㄴ 수 (Gold 1)

요약

  • min과 max가 주어진다.
  • 어떤 1보다 큰 정수의 제곱수로도 나누어 떨어지지 않는 수를 제곱 ㄴㄴ수라고 한다.

분류

  • 에라토스테네스의 체
  • 수학 (로그, 거듭제곱)

풀이

1. 에라토스테네스의 체

  • q에 초기에 주어진 1의 인덱스를 넣는다.
  • bfs 탐색을 시작한다.
  • 일수를 세기 위해 또 다른 예비 리스트 t 를 만든다. q가 다 비면 t를 q에 복사하고 비워준다.

<배운 것들>

  1. deque 와 list는 용도에 따라 구분해서 사용해야 한다.
    • deque : 큐를 다룰 때, 양쪽에서 삭제 및 삽입 가능 (저장 : O(1), 조회 : O(n))
    • list : 빈번한 조회가 이루어질 때 (저장 : O(1) ~ O(n), 조회 : O(1))


import sys
import math
input = sys.stdin.readline

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

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

for d in range(2, int(math.sqrt(MAX)) + 1):
    square = d ** 2

    if square > MAX:
        break

    m = (MIN // square) + 1 if MIN % square != 0 else (MIN // square)

    for i in range(m * square, MAX + 1, square):
        arr[i - 1 - MIN] = False

cnt = 0
for val in arr:
    if val:
        cnt += 1

print(cnt)