코딩하는 해맑은 거북이
[Python] 베르트랑 공준 - 백준 본문
해당 글은 백준 4948번 문제 '베르트랑 공준'을 다룬다.
문제
https://www.acmicpc.net/problem/4948
설명
해당 문제는 소수의 갯수를 구하는 문제이고, 입력받을 때마다 소수를 구하면 시간 제한에 걸리기 때문에
미리 소수를 구해둔 다음에 정해진 범위 내에 소수의 개수를 세는 방식으로 해결해야 한다.
소수를 구하는 방법은 예전 포스팅에서 '에라토스테네스의 체'를 다뤘었다.
이를 이용하면 쉽게 구할 수 있다.
오랜만에 빠르게 소수를 구하는 방법을 되새길수있었다..! 까먹지말자
코드
# 에라토스테네스의 체
arr = [True]*(123456*2+1)
arr[1] = False
for i in range(2, len(arr)):
if arr[i]:
for j in range(i+i, len(arr), i):
arr[j] = False
while True:
n = int(input())
if n == 0:
break
result = 0
for i in range(n+1, 2*n+1):
if arr[i]:
result += 1
print(result)
'코딩테스트' 카테고리의 다른 글
[Python] 그림 - 백준 (DFS) (0) | 2023.08.11 |
---|---|
[Python] 절댓값 힙 - 백준 (0) | 2023.08.11 |
[Python] 오르막 수 - 백준 (DP) (0) | 2023.08.10 |
[Python] 기타줄 - 백준 (DP, 그리디) (0) | 2023.08.10 |
[Python] 최대 힙 - 백준 (0) | 2023.06.16 |
Comments