4948 베르트랑 공준

4948번: 베르트랑 공준 (acmicpc.net)

4948번: 베르트랑 공준

import math
import sys
result = 0
lst = []
def isPrime(num):
    if num == 1:
        return False
    elif num == 2:
        return True
    else:
        for j in range(2, int(math.sqrt(num)) + 1):
            if num % j == 0:
                return False
        return True
for i in range(2, 246913):
    if isPrime(i) == True:
        lst.append(i)
while (1):
    n = int(sys.stdin.readline())
    result = 0
    if n == 0:
        break
    for i in lst:
        if n < i and i <= 2 * n:
            result = result + 1
    print(result)

징차 어이가없다.....

또 시간초과....

소수 최적화도했고 sys.stdin.readline으로도 바꼈는데 시간초과길래 왜그러나했더니

while문을 돌릴때 for문을 숫자가 크면 큰대로 다~~ 참조하면서 소수인지 참고하는 부분에서 시간초과가 뜸

이를 방지하기 위해서는 처음에 소수를 판별해야하는 범위인 (2, 123456 * 2 + 1) 에서 소수인 숫자들만 배열에 정의를 해놓고

이를 for문에서 해당하는 숫자가 만족하는지 판단해야했다. 

범위가 작다면 이를 힌트로 생각하고 가장 큰 수에서 얼마나 오래 걸리는지 판단해 시간을 줄이자.