[백준 4948] 베르트랑 공준 - python (solved.ac - 실버 2)

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

4948번: 베르트랑 공준

풀이

문제를 보았을때 알수있는 힌트

소수!-> 소수 문제는 에라토스테네스의 체 문제라는 것을 인지해두자

그냥 for문으로 풀면 시간초과가 나오니 에라토스테네스의 체로 소수를 찾고 문제를 풀면 쉽게 풀 수 잇는 문제이다.

 

import sys

input = sys.stdin.readline

while True:
    n = int(input())
    if n==0: # 종료 시키기
        break
    n_list=[False,False]+[True]*(2*n)
    result=[1]
    
    for i in range(2,(2*n)+1):
        if n_list[i]:
            result.append(i)
            for j in range(2*i,(2*n)+1,i):
                    n_list[j]=False
    filteredList = [x for x in result if x>n]
    # print(filteredList)
    print(len(filteredList))

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon4948.py