[백준 4948] 베르트랑 공준 python

문제

풀이

처음에 입력받은 수에 대해서 숫자를 세는 방식으로 문제를 풀었는데 시간 초과가 되었다.

가장 큰 수(123456)까지 소수가 아닌지 기억한 후 입력받은 구간에 대해서 소수의 개수를 세는 방식으로 바꿔서 통과되었다.

통과된 풀이

sosu = [0] * (123456 * 2 + 1) 

def isPrime(num):
    if num == 1:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

for i in range(2,len(sosu)):
    if isPrime(i):
        sosu[i] = 1

while True:
    n = int(input())
    if not n:
        break
    print(sum(sosu[n+1:2*n+1]))