[백준] 4948, 베르트랑 공준

https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

---

 N 초과 2N 이하 범위의 소수를 선택하는 알고리즘을 작성하는 문제다. n의 범위는 [ 1, 123456 ] 이므로 현재 문제에서 나타나는 숫자의 범위는 1 ~ 246912 ( 2N )으로 한정된다.

브루트 포스

  가장 큰 숫자인 246912 기준 제곱근을 씌우면 소수 판별을 위해 496번의 연산을 필요로 한다. 이 수치가 상당히 작다고 생각해서 맨 처음에는 N이 들어올 때마다 각각 연산하여 값을 반환하도록 코드를 작성해 봤다.

from sys import stdin
from math import floor
def input():
    return stdin.readline().strip()
# 1이어도 1은 포함 안됨
while True:
    N = int(input())
    if N == 0:
        break
    count  = 0
    for n in range(N + 1, 2*N + 1):
        if n != 2 and n % 2 == 0: 
            continue # 1 또는 2가 아닌 2의 배수는 무시
        cond = True
        for num in range(3, floor(n**0.5) + 1, 2):
            if n % num == 0:
                cond = False
                break
        if cond == True:
            count += 1
    print(count)

## 246913 정도면 메모리가 충분히 커버 가능한 수치

 위 코드는 시간 초과가 발생했다. 한 번에 여러 개의 테스트 케이스를 가지므로 극단적으로 123456이 연속해서 100번 등장하도록 작성되면 대략적으로 425 * 120000 * 100 = 52억 번 이상의 연산을 요구하기 때문에 제한 시간을 맞출 수 없다.

---

소수 계산 후 이진 탐색

 다음으로 생각한 방법은 2 ~ 246912 사이의 소수를 미리 계산하여 저장해 두고, N이 들어올 때마다 N+1 ~ 2N 사이의 소수 개수를 세는 방식이다. 위 언급한 범위 내에는 대략 2만개의 소수가 존재하며, 이 정도의 수치는 N 값에 대해 순차 탐색으로 소수를 직접 세더라도 크게 문제는 없다.

 나는 소수를 구하기 위해 (N,2N) 범위의 소수에 대한 시작 / 끝 인덱스를 이진 탐색 기반으로 각각 얻은 후 두 값을 빼서 개수를 얻는 방법을 생각했다. 코드는 다음과 같다.

from sys import stdin
from math import floor


def input():
    return stdin.readline().strip()
# 이진탐색으로 위치 찾기


def lowbound(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] > target:
            high = mid - 1
        elif arr[mid] <= target:
            low = mid + 1
    return low

def highbound(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] > target:
            high = mid - 1
        elif arr[mid] < target:
            low = mid + 1
        else:
            return mid # high bound는 같은 값이면 바로 반환
    return high

arr = [2]
for n in range(3, 123456 * 2 + 1, 2):
    cond = True
    for num in range(3, floor(n**0.5) + 1, 2):
        if n % num == 0:
            cond = False
            break
    if cond == True:
        arr.append(n)

while True:
    N = int(input())
    if N == 0:
        break
    low = lowbound(arr, N)
    high = highbound(arr, 2 * N)
    # print(low, high, arr[low: high + 1])
    print(high - low + 1)

 범위 내 소수의 최소 인덱스와 최대 인덱스를 구하는 함수가 살짝 다르다. low를 구할 때는 N이 소수인 경우 포함해서는 안되지만, high의 경우 2N이 소수더라도 포함해야 한다. 물론, 2N이 소수인 경우는 N = 1 인 케이스 외에는 존재하지 않는다. 어떤 값에 2를 곱했는데 소수인 경우는 2밖에 없기 때문이다. 

 위와 같은 이유로 N = 2인 케이스를 따로 다룬다면 두 경계를 구하는데 동일한 함수를 사용할 수 있다.

코드는 잘 풀림

---

에라토스테네스의 체

 더 좋은 방식을 찾아보다가, 시간 + 메모리 + 코드 길이가 모두 작은 이상적인 코드를 발견했다. 0 ~ 246912 범위의 숫자들에 대해 소수 여부를 에라토스테네스의 체를 이용하여 판별 후 배열 형태로 저장해두고, N 값이 들어올 때마다 ( N, 2N ] 범위의 소수 개수( True )를 세는 방식으로 동작한다.

from sys import stdin
from math import floor
def input():
    return stdin.readline().strip()
# 0 ~ 123456 * 2 까지
net = [True] * (2 * 123456 + 1)
net[0] = 0
net[1] = 0

for n in range(2, int(len(net) ** 0.5) + 1):
    if net[n]:
        for j in range(2 * n, len(net), n):
            net[j] = False

while True:
    N = int(input())
    if N == 0:
        break
    else:
        print(net[N + 1: 2 * N  +1].count(True))

에라토스테네스의 체의 개념은 대충 알았지만 실제로 사용해 본 적은 없었는데, 이럴 때 사용한다는 것을 알게 되었다.