BAEKJOON-4948 : 베르트랑 공준
BEAKJOON-4948 : 베르트랑 공준Permalink
이 문제는 단순히 소수의 개수를 구하는 문제가 아니다. 매우 일반적인 방법으로 소수의 개수를 구했다면 시간초과가 떳을 것이다. (내가 그랬다 ㅠㅠ) 내가 이 문제를 처음 풀었을 때의 코드는 다음과 같다.
from math import sqrt
x = int(input())
while x:
cnt = 0
for i in range(x+1,x*2+1):
flag = False
for j in range(2,int(sqrt(i))+1):
if i%j == 0:
flag = True
break
if flag:
continue
cnt += 1
print(cnt)
x = int(input())
이 방법은 x+1 부터 2x 까지의 수 중에서 소수의 개수를 구하는 방법이다. 하지만 단점이 있다면 x를 입력할 때마다 해당 구간에서의 소수가 무엇이고, 몇 개인지 확인하는 작업이 반복된다는 점이었다. 이러한 단점 때문에 시간 초과가 떳던 것 같다.
dp를 이용하여 소수를 표시해 놓으면 되겠다고 생각은 했지만 막상 생각하려고 보니 방법이 쉽게 떠오르지 않았다.
그래서 소수를 구하는 방법을 검색해 봤는데 에라토스테네스의 체 라는 소수를 구하는 방법을 알아냈다. (dp를 이용한 방법은 아니었다.)
에라토스테네스의 체를 이용하여 풀었더니 통과했다.
에라토스테네스의 체를 이용한 코드는 다음과 같다.
from math import sqrt
x = 123456*2 + 1
arr = [True] * x
# 에라토스테네스의 체
for i in range(2, int(sqrt(x))+1):
if arr[i]:
for j in range(i+i, x, i):
arr[j] = False
x = int(input())
while x:
if x == 0:
break
cnt = 0
for i in range(x+1, 2*x + 1):
if arr[i]:
cnt +=1
print(cnt)
x = int(input())
우선 첫번째 방법에서 언급했던 단점을 보완하기 위해 문제 조건에서 x의 최대 범위까지 미리 소수가 무엇인지 표시해 놓고, x를 입력하면 해당 구간에서의 소수의 개수를 출력했다.
아주 쏠쏠한 알고리즘을 배운 것 같다. 에라토스테네스의 체 라는 방법을 자주 사용하도록 해서 익혀야겠다.
댓글남기기