[Python] 베르트랑 공준 - 백준

해당 글은 백준 4948번 문제 '베르트랑 공준'을 다룬다.

문제

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

4948번: 베르트랑 공준

 

설명

해당 문제는 소수의 갯수를 구하는 문제이고, 입력받을 때마다 소수를 구하면 시간 제한에 걸리기 때문에

미리 소수를 구해둔 다음에 정해진 범위 내에 소수의 개수를 세는 방식으로 해결해야 한다.

소수를 구하는 방법은 예전 포스팅에서 '에라토스테네스의 체'를 다뤘었다.

이를 이용하면 쉽게 구할 수 있다.

오랜만에 빠르게 소수를 구하는 방법을 되새길수있었다..! 까먹지말자

 

코드

# 에라토스테네스의 체
arr = [True]*(123456*2+1)
arr[1] = False
for i in range(2, len(arr)):
    if arr[i]:
        for j in range(i+i, len(arr), i):
            arr[j] = False

while True:
    n = int(input())
    if n == 0:
        break
    result = 0
    for i in range(n+1, 2*n+1):
        if arr[i]:
            result += 1
    print(result)