[백준] 베르트랑 공준(4948번) - Python

중요 개념

---

1. 소수 탐색

2. 이분탐색법

 

소스코드

---

import sys

def prime(n):
    sieve = [True] * (n+1)
    for i in range(3,int(n**.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i] = [False]*len(sieve[i*i::2*i])
    return [2] + [i for i in range(3,n+1,2) if sieve[i]]

def Search(prime, n):
    l,r = 0, len(prime)-1
    while l<=r:
        m=(l+r)//2

        if prime[m] > n:
            r = m-1
        else:
            l = m+1
    return l

primeList = prime(123456*2)

while True:
    input = int(sys.stdin.readline().strip())
    if input!=0:
        print(Search(primeList,input*2) - Search(primeList,input))
    else:
        break

 

 

 

코드 설명

---

def prime(n:int)->list:
    sieve = [True] * (n+1)
    for i in range(3,int(n**.5)+1,2):
        # 홀수에 대해서만 생각
        if sieve[i]:
            sieve[i*i::2*i] = [False]*len(sieve[i*i::2*i])
            # sieve[i]는 소수 이므로 true이고 seive[i*i] 부터는 소수가 아니다
            # 홀수만 생각하므로 2*i씩 건너 뛴다
    return [2] + [i for i in range(3,n+1,2) if sieve[i]]

prime 함수는 n을 인수로 받아서 n 이하의 소수 list를 리턴한다.

seive (거름망) 

seive list의 index를 해당 숫자로 생각한다.

마지막 return에서 range(3,n+1,2)로 설정해 줌으로써 짝수는 배제하고 n을 포함한 소수 list를 return한다.

 

 

def Search(prime, n):
    left,right = 0, len(prime)-1
    while left<=right:
        #종료 조건 
        m=(left+right)//2

        if prime[m] > n:
            # 찾는 값이 left와 right의 사이보다 오른쪽에 있는 경우
            right = m-1
        else:
            # 찾는 값이 left와 right의 사이보다 왼쪽에 있는 경우
            left = m+1
    return left

Search 함수는 인수로 소수list인 prime과 정수형 변수 n을 받는다.

Search 함수는 prime list에서 n 이하인 최대 소수의 index를 return한다.

 

Search 함수는 이분 탐색 법을 사용하는데 이 문제에서 시간을 대폭으로 줄여줄 수 있다.

 

쉽게 생각하면 소주병 뚜껑으로 하는 UpDown 문제처럼 생각하면 될 것 같다.