[Baekjoon 문제풀이] 1929 - 소수 구하기 (Python 3)

Baekjoon 문제풀이

서론

본 포스팅 시리즈는 필자가 Baekjoon 문제를 풀면서 정리한 코드나 이론을 올리는 포스팅이다.
대부분의 설명은 코드의 주석으로 기재되어있으니 참고바란다.

문제

Baekjoon 1929번 - 소수 구하기:
https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

해법

1차원적으로 생각하면 주어진 범위 내의 숫자를 모두 검사하여 소수일 경우에만 출력해주면 된다. 하지만 문제의 입력값 범위가 1 ≤ M ≤ N ≤ 1,000,000로 주어졌기 때문에 전자와 같이 무식하게 brute force 알고리즘으로 해결하려고 했다간 시간제한 내에 결과를 내지 못할 것이다.

그래서 좀 더 효율적인 알고리즘이 필요한데, 소수를 찾는 알고리즘 중엔 "에라토스테네스의 체"라는 알고리즘이 있다.
중학교 수학 교과서에서 소수를 배우면서 한번쯤은 들어봤을 것이다.
이 알고리즘은 소수의 배수는 소수가 아니라는 점에서 착안되었다. 주어진 값을 통해 배열을 생성하고 에라토스테네스의 체를 이용해 해당 배열에 소수가 아닌 인덱스의 요소를 마킹해가면서, 마킹된 부분은 검사를 하지 않는 방법으로 작업량을 줄여 시간복잡도를 줄이게 된다.

에라토스테네스의 체에 대한 자세한 내용은 참고자료의 링크를 참고 바란다.

풀이

참고자료

위키피디아 - 에라토스테네스의 체:
https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전