[BOJ] 베르트랑 공준(4948) - PYTHON

1 <= n <=123,456 사이의 n이 입력으로 들어오면 (n + 1) ~ 2n 사이의 소수 개수를 구하는 문제다. 베르트랑 공준에 의해 소수 개수는 1개 이상 존재한다.

시간 복잡도: O(N + logN)

4948번: 베르트랑 공준

---

풀이 과정

우선 (n + 1) ~ 2n 사이의 소수가 얼마나 있는 지를 구해야 한다. 문제에서 주어진 조건에 의해 n은 123,456 이하의 자연수이며, 입력이 0이 들어오기 전까지 로직이 반복되므로 123456 * 2 이하의 소수들을 먼저 구한다. 소수를 구하는 방법은 에라토스테네스의 체를 활용한다. 설명은 위키피디아에 잘 나와있어서 대체한다.

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

이후 각 입력마다 n보다 큰 소수의 최솟값 index 값을 구하고, 2n보다 작거나 같은 소수의 최댓값 index를 구하고 그 둘의 차이를 통해 소수의 개수를 구한다.
index를 구하는 방법은 이분 탐색을 활용해서 O(logN) 시간에 구한다. 이때 목표값을 정확히 찾는 것이 아니라 목표값보다 큰 값 중 최소값, 목표값보다 작거나 같은 값 중 최댓값을 구하는 것이므로 아분 탐색을 변형해서 사용한다. 코드에서 n보다 큰 소수의 최소값을 구하는 로직을 uppperbound라 했고, 2n보다 작거나 같은 소수의 최대값을 구하는 로직을 lowerbound라 했다.
( ※ lowerbound의 경우 실제 알고리즘 학계에서 쓰이는 lowerbound와는 의미가  다르다.)

이렇게 되면 n이 입력으로 들어올 때 우선 에라토스테네스의 체를 이용해 1 ~ 2n까지의 소수들을 구하는데 O(N)의 시간이 걸린다. 또 n, 2n에 대해 upperbound, lowerbound을 구하는데 O(logN)의 시간이 걸린다. 따라서 총 걸리는 시간은 O(N + logN)이다.

---

코드

def getPrimeArr(num):  
    primeArr = [True] * (num + 1)  
    primeArr[0] = False
    primeArr[1] = False  
    for i in range(2, num + 1):  
        if primeArr[i]: 
            temp = i + i  
            while temp <= num: 
                primeArr[temp] = False  
                temp += i  
    primeArr = [i for i in range(len(primeArr)) if primeArr[i]]  
    return primeArr  
 
def lowerBound(s, e, target, arr):  
    if s > e:  
        return e  
    mid = (s + e) // 2  
    if arr[mid] < target:  
        return lowerBound(mid + 1, e, target, arr)  
    elif arr[mid] > target:  
        return lowerBound(s, mid - 1, target, arr)  
    else:  
        return mid  
 
 
def upperBound(s, e, target, arr):  
    if s > e:
        return s
    mid = (s + e) // 2
    if arr[
        mid] <= target:  
        return upperBound(mid + 1, e, target, arr)
    elif arr[mid] > target:
        return upperBound(s, mid - 1, target, arr)
 
 
if __name__ == "__main__":
    primeArr = getPrimeArr(300000)  
    while True:  
        n = int(input())
        if n == 0:
            break
        lb = upperBound(0, len(primeArr), n, primeArr)
        ub = lowerBound(0, len(primeArr), n * 2, primeArr) # 2n에대해 lowerBound 구하기
        print(ub - lb + 1)
 

 

주석 추가

def getPrimeArr(num):  # num보다 작거나 같은 소수 배열 구하기
    primeArr = [True] * (num + 1)  # 각 숫자에 대해 소수 여부를 저장할 배열 (초기 값은 모두 소수)
    primeArr[0] = False
    primeArr[1] = False  # 0,1은 소수 아님
    for i in range(2, num + 1):  # 2~num에 대해서
        if primeArr[i]:  # 현재 수가 소수라면
            temp = i + i  # 현재 수의 배수는 소수가 아님
            while temp <= num:  # 현재 수의 배수가 num보다 작을 동안
                primeArr[temp] = False  # 소수가 아님을 표시
                temp += i  # i를 더해서 다음 배수로 넘어감
    primeArr = [i for i in range(len(primeArr)) if primeArr[i]]  # 판별된 소수 여부 배열을 통해 소수인 숫자 목록을 담은 배열 생성
    return primeArr  # 생성된 배열 반환
 
 
def lowerBound(s, e, target, arr):  # target보다 작거나 같은 값중 최대값idx 구하기 (s: 시작idx, e: 끝idx, target: 찾는 값, arr: 배열)
    if s > e:  # 시작idx가 끝idx보다 크다면
        return e  # 끝 idx 반환
    mid = (s + e) // 2  # 중앙값 구하기
    if arr[mid] < target:  # 중앙값이 찾는 값보다 작다면
        return lowerBound(mid + 1, e, target, arr)  # 시작값idx를 중앙값idx + 1로 업데이트
    elif arr[mid] > target:  # 중앙값이 찾는 값보다 크다면
        return lowerBound(s, mid - 1, target, arr)  # 끝값idx를 중앙값idx - 1로 업데이트
    else:  # 중앙값 == 찾는 값이라면
        return mid  # 중앙값의 idx 반환
 
 
def upperBound(s, e, target, arr):  # target보다 큰 값 중 최소값idx 구하기 (lowerBound에서 29, 31번째 줄만 다름)
    if s > e:
        return s
    mid = (s + e) // 2
    if arr[
        mid] <= target:  # 문제에서는 target보다 처음으로 큰 값이 나오는 idx를 구해야하므로 arr[mid] == target 일때의 조건을 arr[mid] < target일때의 로직과 같이 처리
        return upperBound(mid + 1, e, target, arr)
    elif arr[mid] > target:
        return upperBound(s, mid - 1, target, arr)
 
 
if __name__ == "__main__":
    primeArr = getPrimeArr(300000)  # 30만까지의 소수를 구하기(123456 * 2까지의 소수만 구해도 되지만 lowerBound를 구할때 indexError가 발생해 여유롭게 잡음)
    while True:  # n이 0이들어올때까지 반복
        n = int(input())
        if n == 0:
            break
        lb = upperBound(0, len(primeArr), n, primeArr) #n에대해 upperBound 구하기
        ub = lowerBound(0, len(primeArr), n * 2, primeArr) # 2n에대해 lowerBound 구하기
        print(ub - lb + 1)
 

---

채점 결과

이분 탐색으로 값을 구하는데 실수가 있어 3번 만에 성공했다.