BAEKJOON-4948 : 베르트랑 공준

BEAKJOON-4948 : 베르트랑 공준

이 문제는 단순히 소수의 개수를 구하는 문제가 아니다. 매우 일반적인 방법으로 소수의 개수를 구했다면 시간초과가 떳을 것이다. (내가 그랬다 ㅠㅠ) 내가 이 문제를 처음 풀었을 때의 코드는 다음과 같다.

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를 입력하면 해당 구간에서의 소수의 개수를 출력했다.

아주 쏠쏠한 알고리즘을 배운 것 같다. 에라토스테네스의 체 라는 방법을 자주 사용하도록 해서 익혀야겠다.