4928. 베르트랑 공준 - 시간 초과

시간 초과 코드

에라토스테네스의 체를 사용하였다. 루트를 이용하여 n번 확인할 것을 루트 n만큼 계산량을 줄이는 것이 포인트이다.

결과 값은 정확하게 출력된다. 하지만 시간 초과가 났다. 

from math import sqrt

def is_prime_num(n):
    if n == 1:
        return False

    for i in range(2, int(sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

while True:
    num = int(input())
    cnt = 0

    if num == 0:
        break

    for i in range(num + 1, 2 * num + 1):
        if is_prime_num(i):
            cnt += 1

    print(cnt)

 

해결 방안 분석

이를 해결하기 위한 힌트는 바로 실행 횟수와 관련이 있다. 해당 문제를 살펴보자.

입력과 출력이 한번만 이루어지는 것이 아니라, 0이 들어올 때까지 같은 계산 방식을 여러번 취하는 것이다.

이 말에 힌트가 있다. 같은 연산을 반복한다. 즉, 동일한 연산을 반복적으로 하는 비효율이 있다는 것을 인지 할 수 있다.

 

결과 코드

같은 범위를 지속적으로 조회하지 않기 위해서 prime_num이라는 배열을 만들고 미리 연산을 한다.

여기서 주의 할 점은 prime_num 배열 크기는 고민해 보길 바란다.

from math import sqrt

prime_num = [True] * (2 * 123456 + 1)
prime_num[0] = prime_num[1] = False

def is_prime_num(n):
    if n == 1:
        return False

    for i in range(2, int(sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

if __name__ == '__main__':

    for pn in range(len(prime_num)):
        if is_prime_num(pn):
            prime_num[pn] = True
        else:
            prime_num[pn] = False

    while True:
        num = int(input())
        cnt = 0

        if num == 0:
            break

        for i in range(num + 1, 2 * num + 1):
            if prime_num[i]:
                cnt += 1

        print(cnt)