[Python] 백준 4948번 : 베르트랑 공준

Problem

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

Solution

def prime_list(n):
    sieve = [True] * n
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:
            for j in range(i+i, n, i):
                sieve[j] = False

    return [i for i in range(2, n) if sieve[i] == True]

n = int(input())
while n:
    final_list = [i for i in prime_list(2*n+1) if i>n]
    print(len(final_list))
    n = int(input())

Memo

소수판별 알고리즘인 에라토스테네스의 체를 활용하였다.