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

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

4948번: 베르트랑 공준

풀이

주어진 입력값보다 크거나 입력값의 2배보다 작거나 같은 소수들의 개수를 계산하는 문제입니다.

에라토스테네스의 체 알고리즘을 이용하여서 1에서 입력값의 최댓값인 123456의 2배인 246912까지의 숫자 중에서 소수들을 찾아줍니다. 주어지는 값에 따라 소수의 개수를 계산해주면 됩니다.

 

에라토스테네스의 체(소수 찾기 알고리즘): https://sunghyun98.tistory.com/33

 

# 4948번 베르트랑 공준
import sys
def sieve():    # 에라토스테네스의 체 알고리즘.
    n = 123456*2
    arr = [True for _ in range(n+1)]
    for i in range(2, int(n**0.5)+1):
        if arr[i]:
            for j in range(i*2, n+1, i):
                arr[j] = False
    return arr   # 소수들의 목록을 반환
    
def solve():
    sosu_li = sieve()
    while True:
        k = int(sys.stdin.readline())
        if k==0:
            break
        n = 2*k
        ans = 0
        for i in range(n//2+1, n+1):    # 소수들의 개수를 계산하기위해 범위 조정
            if sosu_li[i]:
                ans += 1
        print(ans)
        
solve()

출력결과