백준 4948 베르트랑 공준 (Python)

https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

 

일단 당연히 소수와 관련된 문제이기에 에라토스테네스의 체를 사용해서 풀었다.

https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

에라토스테네스의 체

 

그렇게 풀었어도 시간 문제가 발생했었는데, 입력이 있을 때마다 계산을 해서 출력을 했기 때문이었다.

import sys

while True:
    n = int(sys.stdin.readline().strip())

    if n == 0:
        break

    number = [True for i in range(2 * n + 1)]

    for i in range(2, int((2 * n + 1) ** 0.5) + 1):
        if number[i]:
            for t in range(i + 1, 2 * n + 1):
                if t % i == 0:
                    number[t] = False

    print(number[n + 1: 2 * n + 1].count(True))

 

이렇게 풀었는 데, 시간 문제가 발생해서

입력을 받기 전에 계산을 모두 해두고, 출력만 바로바로 할 수 있도록 하였다,

 

import sys

number = [True for i in range(123456 * 2 + 1)]

for i in range(2, int((2 * 123456 + 1) ** 0.5) + 1):
    if number[i]:
        for t in range(i + 1, 2 * 123456 + 1):
            if t % i == 0:
                number[t] = False


while True:
    n = int(sys.stdin.readline().strip())

    if n == 0:
        break

    print(number[n + 1: 2 * n + 1].count(True))

 

이렇게 풀었더니 시간 문제가 발생하지 않았다.