<백준 문제풀이: 4948번> 베르트랑 공준

다른 소수문제랑 비슷한 문제이지만, 이번 문제도 시간 초과 때문에 너무나도 많은 시행착오를 거쳐야 했다:

시간초과 뜬 방식 - (1)

import sys

while True:
    N = int(sys.stdin.readline())
    if N == 0:
        break
    num = set(range(2, 2*N+1))
    for i in range(2, 2*N+1):
        if i in num:
            num -= set(range(2*i, 2*N+1, i))
    count = 0
    for j in range(N+1, 2*N+1):
        if j in num:
            count += 1
    print(count)

시간초과 뜬 방식 - (2)

import sys

while True:
    N = int(sys.stdin.readline())
    if N == 0:
        break
    count = 0
    for i in range(N+1, 2*N+1):
        if i == 1:
            continue
        elif i == 2:
            count += 1
            continue
        else:
            for j in range(2, int(i**0.5)+1):
                if i%j == 0:
                    break
            else:
                count += 1
    print(count)

시간초과가 왜 떴는지 생각해보니, 단순히 모든 숫자에 대해 지속적으로 소수를 찾아보려고 하니까 그런 듯 했다. 따라서 다음의 방식과 같이 미리 소수들을 구해주고 그 다음에 해당 범위 안에 있는 소수들의 개수를 찾는 것으로 했다:

나의 풀이

import sys

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

all_num = [x for x in range(123456*2+1)]
prime_list = []

for i in all_num:
    if is_prime(i):
        prime_list.append(i)

while True:
    N = int(sys.stdin.readline())
    if N == 0:
        break
    count = 0
    for i in prime_list:
        if N < i <= 2*N:
            count += 1
    print(count)

문제에 주어진 N의 최댓값에 대하여 미리 소수들을 구해주고, while문에는 문제에서 요구하는 범위 안에 소수들이 포함되어 있으면 count를 1씩 늘려주는 방식으로 구했다.