[백준 문제풀이] 4948 - 베르트랑 공준

백준 문제풀이 4948번

풀이

기본적으로 에라토스테네스의 체 알고리즘을 사용하고, 범위가 123456이라는 점을 활용해 속도를 높힐 수 있다.

코드

import sys

input = sys.stdin.readline

arr = [0] * 2 + [1] * 246912 # 123456까지 수 제한이 있으므로 2n의 범위인 246912까지 배열 선언

for i in range(2, 246913):
    if arr[i]:
        for j in range(i * 2, 246913, i): # 에라토스테네스의 체에서 소수의 배수를 없애는 순서
            arr[j] = 0

while True:
    num = int(input())
    if num == 0:
        break
    print(sum(arr[num+1:num*2+1]))