[파이썬, Python] 백준 4948: 베르트랑 공준

문제

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

4948번: 베르트랑 공준

코드

prime = []

for i in range(2, 246913):
    cnt = 0
    for j in range(2, int(i**0.5)+1):
        if i % j == 0:
            cnt += 1
            break
    if cnt == 0:
        prime.append(i)

while True:
    n = int(input())
    primecnt = 0
    
    if n == 0:
        break
    for i in prime:
        if n < i <= 2*n:
            primecnt += 1
    print(primecnt)

설명

계속 시간초과에 걸려서 고민했던 문제였다.

핵심은 범위가 주어져 있으므로 미리 소수를 계산해놓은 리스트를 만드는 것이었다.

미리 반복문을 한 번 돌려 리스트를 만들어놓고,
아래의 조건문에선 소수의 유무만을 체크하면 되는 문제였다.

문제 자체는 이전의 문제들에서 볼 수 있는 유형이었으나 시간 초과를 조금 생각하게 되는 문제였다