[Python]백준 - 베르트랑 공준(4948번)

문제출처 - https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

시간초과 뜬 코드

import math

def isPrime(num):
    if num == 1: return False

    for i in range(2, int(math.sqrt(num))+1):
        if num % i == 0: return False

    return True


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

    for i in range(n+1, 2*n+1):
        if isPrime(i):
            answer += 1

    print(answer)

매번 입력할때마다 소수를 구해서 시간초과 뜬 듯..

 

성공한 코드

import math

def isPrime(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))
prime_li = []
for i in li:
    if isPrime(i):
        prime_li.append(i)

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

    for i in prime_li:
        if n < i <= n*2:
            answer += 1

    print(answer)

미리 123456의 2배인 246912 사이에 있는 소수를 구해 그 리스트에서 비교함