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

🥚문제

---

🥚입력/출력

---

🍳코드

from sys import stdin
input = stdin.readline

m, n = map(int, input().split())

# 에라토스테네스의 채
# 빠른 검색에 최적화된 set 자료구조 이용
# 소수임을 알고있는 2부터 값을 넣음
eratos = {x for x in range(2, n+1)}

target = 2
# n의 제곱근까지만 구하면 된다
while target*target <= n:
    # target이 이미 제외되었을 때
    if target not in eratos:
        target += 1
        continue

    # target의 배수들을 탐색한다
    # target*2, target*3, target*4, ...
    for i in range(target*2, n+1, target):
        # target의 배수들을 제외한다
        # discard는 set 내에 i값이 없어도 에러가 나지 않음
        eratos.discard(i)

    # 다음 탐색을 위해 target 값 증가
    target += 1

# m 이상 n 이하인 소수 출력
# 집합 eratos를 내림차순으로 정렬된 리스트로 바꿈
eratos_list = sorted(list(eratos), reverse=True)
# m이상 n이하인 소수를 저장하는 리스트
prime_list = []

for prime in eratos_list:
    # m 이상인 것만 prime_list에 저장
    if prime >= m:
        prime_list.append(prime)
    # m 미만이면 저장하지 않는다
    else:
        break

# 다시 prime_list를 내림차순으로 정렬한 뒤 소수 하나씩 출력
if len(prime_list) > 0:
    for prime in sorted(prime_list):
        print(prime)
else:
    print()

---

🧂아이디어

• 에라토스테네스의 체를 이용하여 빠르게 구하는 것이 핵심
• 소수 구하기 테크닉들 복습하기 (에라토스테네스의 채, 왜 제곱근까지만 구하면 되는지...)
• 어떤 자료구조를 사용하는지도 중요