BOJ/백준-4948-python

문제📖

풀이🙏

• 입력은 여러 개의 케이스로 이루어져 있다.
• 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.
• 입력의 마지막에는 0이 주어진다.
• 각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.
  -> 에라토스테네스의 체 + 제너레이터 표현식으로 구현하였다.

코드💻

# boj, 4948 : 베르트랑 공준, python3
# 수학, 정수론, 소수 판정, 에라토스테네스의 체 알고리즘
import sys

def eratos(n):
    sieve = [1] * (n + 1)

    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i]:
            for j in range(i * 2, n + 1, i):
                sieve[j] = 0

    return sum([1 for i in range(2, n + 1) if sieve[i] and i > n/2])


def solve(n):
    return eratos(2*n)


while True:
    n = int(sys.stdin.readline())
    
    if n == 0:
        break
    
    print(solve(n))

결과😎

출처 && 깃허브📝

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