[파이썬] 백준 알고리즘 No.4948 베르트랑 공준

백준 4948번 베르트랑 공준 문제

 

에라토스테네스의 체를 이용했던 문제와 유사하다.

체를 이용해 주어진 수의 범위를 n ~ 2n으로 설정하여 소수가 나올때마다 count를 올려주기만 하면 된다.

 

import math
import sys
input = sys.stdin.readline

start = 1
while True:
    start = int(input())
    if start == 0:
        break
    end = 2 * start
    count = 0

    if start == 1:
        print("1")
        continue

    array = [True for i in range(end + 1)]

    for i in range(2, int(math.sqrt(end)) + 1):
        if array[i]:
            j = 2
            while i * j <= end:
                array[i * j] = False
                j += 1

    for i in range(start + 1, end + 1):
        if array[i]:

            count += 1

    print(count)