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

문제 출처 : https://www.acmicpc.net/problem/4948

기존 코드 💻

📘 시간 초과

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

while True :
    case = int(input())
    cnt = 0
    if case == 0 :
        break
    for i in range(case+1, 2*case+1) :
        if isPrime(i) :
            cnt += 1
    print(cnt)

👉🏻 에라토스테네스의 체를 이용해서 범위 안의 모든 값을 확인했는데 모든 값 확인 과정에서 CPU과부하가 생겨서 시간초과가 발생했다.

수정 코드 💻

from math import sqrt

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

case = list(range(2,246912))
sort = []
for i in case :
    if isPrime(i) :
        sort.append(i)

while True :
    n= int(input())
    cnt = 0
    if n == 0 :
        break
    for i in sort :
        if n < i <= 2*n :
            cnt += 1
    print(cnt)

👉🏻 문제에서 제한한 범위 1 <= n <=123,456 안에서의 소수만 저장하고 for 문을 돌리는 동안 소수 리스트에 있는 소수들을 꺼내오는 방식으로 해결했다.

느낀 점 ✏️

범위가 주어지면 그것도 확인해봐야겠다.
오늘도 파이팅🥰