728x90
백준 1929번: 소수 구하기
📌 문제
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000)
M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
📝 문제 접근 방법
문제 요약
- 주어진 범위 $[M, N]$ 에서 모든 소수를 찾아 출력합니다.
- 입력 범위는 최대 1,000,000까지 가능하므로 효율적인 소수 판별이 필요합니다.
아이디어
1. 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘
범위 내의 소수를 효율적으로 구하는 알고리즘으로
소수를 판별하는 데 불필요한 연산을 줄이기 위해 작은 소수의 배수를 반복적으로 제거하는 방식
- 작동 원리
- 초기화
- 범위 $[2, N]$ 까지의 모든 수를 소수(True)로 가정합니다.
- 특별히 0과 1은 소수가 아니므로 False로 설정합니다.
- 배수 제거
- 2부터 시작하여, 현재 숫자가 소수(True)라면 그 배수들을 모두 제거합니다.
- 배수 제거는 현재 수의 제곱부터 시작합니다.
- 이유: 그 이전의 배수들은 이미 이전 단계에서 처리되었기 때문입니다.
- 이 과정은 $\sqrt{N}$까지만 반복하면 됩니다.
- 이유: 약수의 대칭적 관계 때문에 $\sqrt{N}$ 까지만 확인하면 모든 약수쌍을 파악할 수 있습니다.
- 결과 확인
- 배수 제거가 끝난 후 리스트에서 True로 남아 있는 숫자들은 모두 소수입니다.
- 초기화
👩💻 나의 답안
import math
m, n = tuple(map(int, input().split()))
array = [True] * (n + 1)
array[0] = array[1] = False
for i in range(2, int(math.sqrt(n)) + 1):
if array[i]:
for j in range(i * i, n + 1, i):
array[j] = False
for i in range(m, n + 1):
if array[i]:
print(i)
✨ 새로 알게 된 점
1. 에라토스테네스의 체
에라토스테네스의 체는 소수 판별에서 가장 효율적인 알고리즘 중 하나로, 소수의 배수를 제거하여 연산량을 줄이는 방식을 사용합니다. 특히 배수를 제거할 때 i * i부터 시작하는 이유는 그 이전의 배수는 이미 처리되었기 때문이며 약수의 대칭적 관계를 활용해 $\sqrt{N}$까지만 탐색하면 충분하다는 점도 알게 되었습니다. 또한 Python의 math.sqrt()를 사용해 제곱근을 계산하고 탐색 범위를 제한하는 방식으로 에라토스테네스의 체를 간단히 구현할 수 있음을 알았습니다. 이 알고리즘은 최대 범위가 1,000,000까지 주어지더라도 O(Nlog(log N))의 시간 복잡도로 효율적으로 동작한다는 점도 확인할 수 있었습니다.
728x90
반응형
'코딩테스트 대비' 카테고리의 다른 글
[파이썬(Python)] 백준 1676번 팩토리얼 0의 개수 (0) | 2024.11.29 |
---|---|
[파이썬(Python)] 백준 6588번 골드바흐의 추측 (0) | 2024.11.28 |
[파이썬(Python)] 백준 1978번 소수 찾기 (0) | 2024.11.27 |
[파이썬(Python)] 백준 2609번 최대공약수와 최소공배수 (0) | 2024.11.26 |
[파이썬(Python)] 백준 11656번 접미사 배열 (0) | 2024.11.18 |