서론
본 포스팅 시리즈는 필자가 Baekjoon 문제를 풀면서 정리한 코드나 이론을 올리는 포스팅이다.
대부분의 설명은 코드의 주석으로 기재되어있으니 참고바란다.
문제
Baekjoon 4948번 - 베르트랑 공준
https://www.acmicpc.net/problem/4948
4948번: 베르트랑 공준
베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼
www.acmicpc.net
해법
이번 문제는 주어진 정수 N에 대하여, N보다 크고 2N보다 작거나 같은 소수의 개수를 출력하는 문제다. 이번 문제도 에라토스테네스의 체를 사용하면 쉽게 해결할 수 있는데, 다만 테스트케이스가 여러개가 주어지기 때문에 에라토스테네스로 필터링이 된 정보를 저장해둔다면 공간복잡도 O(1)로 해결할 수 있다. 그리고 필터링이 된 마지막 소수를 저장해두어 이미 필터링이 된 소수의 배수들에 대해서 불필요한 작업을 반복하지 않도록 할 수 있다.
풀이
참고자료
위키피디아 - 에라토스테네스의 체:
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 문제풀이] 1463 - 1로 만들기 (Python 3) (0) | 2022.01.10 |
|---|---|
| [Baekjoon 문제풀이] 1934 - 최소공배수 (Python 3) (0) | 2022.01.06 |
| [Baekjoon 문제풀이] 1011 - Fly me to the Alpha Centauri (Python 3) (0) | 2022.01.06 |
| [Baekjoon 문제풀이] 11653 - 소인수분해 (Python 3) (0) | 2022.01.04 |
| [Baekjoon 문제풀이] 4153 - 직각삼각형 (Python 3) (0) | 2022.01.04 |