[python] 백준 - 4948. 베르트랑 공준

🤔문제 해결

• S2 | 에라토스테네스의 체

1. 에라토스테네스의 체를 사용하여 소수를 구하고 시작.

주어진 구간에 맞게 소수의 개수를 꺼냄

 

 

💻소스 코드

import sys


def eratos(n):
    for j in range(n * 2, 123456 * 2 + 1, n):
        dp[j] = 0


dp = [1] * (123456 * 2 + 1)
dp[0], dp[1] = 0, 0
for i in range(2, 123456 * 2 + 1):
    if dp[i] == 1:
        eratos(i)
input = sys.stdin.readline
while True:
    N = int(input())
    if N == 0:  # 입력 마지막
        break
    print(sum((dp[N + 1:N * 2 + 1])))

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

4948번: 베르트랑 공준