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

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

4948번: 베르트랑 공준

 

1929번 문제에서 범위 제한만 하면 되네~하고 풀었지만 시간 초과😤💧

 

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

    if n == 0:
        break

    for i in range(n+1, 2*n+1):
        for p in range(2, int((2*n)**0.5)+1):
            if i % p == 0:
                cnt += 1
                break

    print(n-cnt)

 

각 테스트 케이스마다 계속 소수를 계산하니까 시간 초과가 난 것 같다!

그래서 문제에서 주어진 범위 내에서 소수를 먼저 모두 구해놓고 범위를 제한했다

 

num = []

for i in range(2, 246913):
    cnt = 0

    for p in range(2, int(i**0.5)+1):
        if i % p == 0:
            cnt += 1
            break

    if cnt == 0:
        num.append(i)

while True:
    n = int(input())
    res = 0

    if n == 0:
        break

    for i in num:
        if n < i <= 2*n:
            res += 1

    print(res)