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

문제

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

4948번: 베르트랑 공준

 

접근 방법

전형적인 에라토스테네스의 체 문제이다.

n의 범위가 최대 123456까지이므로 넉넉하게 25만까지의 소수를 미리 구해놓으면 쉽게 계산할 수 있다.

 

코드

import sys
import math
from bisect import bisect_right

MAX_N = 250000
isPrime = [True] * MAX_N # isPrime[i]는 i가 소수인지 유무를 나타냄
isPrime[0] = False
isPrime[1] = False

for i in range(math.floor(math.sqrt(MAX_N))):
    if isPrime[i] == False:
        continue
    j = 2
    while i * j < MAX_N:
        isPrime[i * j] = False
        j += 1
        
primeArr = [i for i in range(MAX_N) if isPrime[i] == True] # 소수들만 모은 배열

while True:
    n = int(sys.stdin.readline().rstrip())
    if n == 0:
        break
    
    print(bisect_right(primeArr, 2 * n) - bisect_right(primeArr, n)) # n초과 2n이하 소수의 개수

 

풀이 정보

시도 횟수: 1회

총 문제 풀이에 걸린 시간: 9분 30초