백준의 알고리즘 4948번 문제(python)

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

4948번: 베르트랑 공준

주어진 n에 대해 n~2n까지의 소수의 갯수를 구하는 문제이며 소수구하는 문제를 풀어봤으니 쉽게 구할 수 있을 것이라 생각하고 풀었다

import math

n=[]
sosu=[]
while 1:
    i=int(input())
    n.append(i)
    if(i==0):
        n.pop()
        break

for i in n: # 주어진 입력값들 반복
    sosu=0
    if(i==1):
        sosu=1
        print(sosu)
        continue
    for j in range(int(i),(int(i)*2)+1): # 입력값의 n~2n사이 반복
        count=0
        for k in range(2,int(math.sqrt(j)+1)): # 사이에 소수가 몇개있는가    
            if(j%k==0):
                count+=1
                break
        if(count==0):
            sosu+=1

    print(sosu)

위의 코드가 완성되었고 시간초과의 벽에 막혀서 방법을 찾고있었다

# 4948번 문제 : 베르트랑 공준
# 주어진 n에 대해 n~2n사이에 소수를 구하는 문제이다

import math #sqrt()를 사용하기 위함

def sosu(num): # 소수를 수하는 함수
    if num == 1: 
        return False

    for i in range(2, int(math.sqrt(num))+1): # 주어진 수의 제곱근까지만 체크해보면 된다
        if num % i == 0: 
            return False

    return True


li = list(range(2,246912)) # 최대수인 123456의  2배를 미리 리스트의 넣는다

k = []

for i in li: # 246912안에 소수들을 미리 구해놓는다
    if sosu(i):
        k.append(i)

while(1):
    answer = 0
    n = int(input())
    if n == 0: 
        break

    for i in k: # 미리 구해놓는 소수가 주어진 수의 범위안에 몇개가 있는지만 체크
        if ((n < i) and (i <= n*2)):
            answer+=1
    print(answer)

원인은 수가 주어질때마다 소수를 구하는것이였고 생각해보니 소수는 정해져있기때문에 가장 큰 수 이하의 소수를 구해서 문제를 해결했다. 언제나 정답은 도출해내지만 시간초과의 벽에 막혀 헤매는걸 보고 좀 더 연습해야 겠다는 생각을 한다