[백준] 4948번 : 베르트랑 공준 (파이썬)

문제

나의 첫번째 답안(시간초과)

import sys
input=sys.stdin.readline

while True:
    n=int(input())
    if n==0:
        break
    cnt=0
    for i in range(n+1,n*2+1):
        if i==1:
            continue
        elif i==2:
            cnt+=1
            continue
            
        else:
            for j in range(2,int(i**(1/2))+1):
                if i%j==0:
                    break
            else:
                cnt+=1
   
    print(cnt)

일반적으로 소수 구하는 것처럼 문제를 접근했더니 시간초과라는 결과가 나왔다.

나의 최종 답안

import sys
input=sys.stdin.readline

sosu=[]

for i in range(2,246913):
    cnt=0
    
    for j in range(2,int(i**(1/2))+1):
        if i%j==0:
            cnt+=1
            break
        
    if cnt==0:
        sosu.append(i)
            
while True:
    n=int(input())
    re=0
    if n==0:
        break
    
    for k in sosu:
        if n<k and k<=n*2:
            re+=1
    print(re)

접근 방식

• 문제에서 제시한 1 ≤ n ≤ 123,456 범위에 따라 사전에 소수를 구해주었다.
• 이후 0을 입력받을 때까지 n부터 n*2까지의 소수 개수를 카운트 해준다.