[백준/파이썬] 4948번 - 베르트랑 공준

문제 설명

풀이 전략

1929번-소수 구하기와 매우 유사한 문제이다. 소수 관련 문제는 에라토스테네스의 체를 이용하는 것이 가장 효율적이다. 입력 테스트 케이스가 여러개 이므로 매 번 소수를 구하는 것이 아닌 n이 123,456 이하의 수 이므로 $2*123,456$ 까지 소수를 구해놓고 매 반복 시 해당 범위의 개수를 세는 방식으로 해결한다.

코드

# 에라토스테네스의 체로 2*123456 까지의 소수 구하기
k=123456*2
sieve = [False, False] + [True] * (k-1)
primes=[]
for i in range(2,k+1):
    if sieve[i]:
        primes.append(i)
        for j in range(2*i,k+1,i):
            sieve[j] = False
# 입력 테스트가 주어지면 소수 리스트에서 개수를 세어 출력
while True:
    n = int(input())
    if n == 0:
        break
    count = 0
    for element in primes:
        if element > 2*n:
            break
        elif n < element:
            count += 1
    print(count)