https://www.acmicpc.net/problem/4948
4948번: 베르트랑 공준
베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼
www.acmicpc.net
접근 :
- 정수론을 이용하여 특정 범위 내 소수의 갯수를 구한다
- 누적합을 이용하여 시간을 줄인다
( 누적합을 이용하지 않는 경우 : 메모리 35688 KB , 소요 시간 4756 ms / 사용한 경우 : 메모리 33124 KB , 소요 시간 540 ms )
* 사전 범위를 파악하여 가능하면 누적 합을 이용하는 것을 판단해보는 것이 중요
코드 구현 :
'Python > Coding TEST' 카테고리의 다른 글
| [Python] 백준 13909 창문 닫기 (0) | 2024.02.18 |
|---|---|
| [Python] 백준 1929 소수 구하기 (1) | 2024.02.11 |
| [Python] 백준 4134 다음 소수 (0) | 2024.02.10 |
| [Python] 백준 2485 가로수 (0) | 2024.02.10 |
| [Python] 백준 1735 분수 합 (0) | 2024.02.09 |