서론
본 포스팅 시리즈는 필자가 Baekjoon 문제를 풀면서 정리한 코드나 이론을 올리는 포스팅이다.
대부분의 설명은 코드의 주석으로 기재되어있으니 참고바란다.
문제
Baekjoon 2581번 - 소수:
https://www.acmicpc.net/problem/2581
2581번: 소수
M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.
www.acmicpc.net
해법
이번 문제는 자연수 M과 N이 주어질때 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 이들의 총합과 최솟값을 찾는 문제이다. 일단 "소수"라는 단어에서 알 수 있듯이 이번 문제는 "에라토스테네스의 체"를 이용하면 쉽게 해결할 수 있다.
이전 문제(1929번)에서도 설명했듯이 에라토스테네스의 체의 컨셉은 "소수의 배수는 소수가 아니다"라는 것이다. 이를 이용하여 소수를 검색하고 검색된 소수의 배수를 마킹하여 소수가 아닌 수에서는 불필요한 검색 작업을 수행하지 않는다.
풀이
참고자료
위키피디아 - 에라토스테네스의 체:
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
에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전
수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서
ko.wikipedia.org
'SW > Baekjoon' 카테고리의 다른 글
| [Baekjoon 문제풀이] 9461 - 파도반 수열 (Python 3) (0) | 2022.01.04 |
|---|---|
| [Baekjoon 문제풀이] 2748 - 피보나치 수 2 (Python 3) (0) | 2022.01.04 |
| [Baekjoon 문제풀이] 2609 - 최대공약수와 최소공배수 (Python 3) (0) | 2022.01.04 |
| [Baekjoon 문제풀이] 1085 - 직사각형에서 탈출 (Python 3) (0) | 2022.01.04 |
| [Baekjoon 문제풀이] 1929 - 소수 구하기 (Python 3) (0) | 2022.01.04 |