BAEKJOON PYTHON 4948 베르트랑 공준

Prob

---

Approach

1은 소수가 아니다.

시간 초과가 관건. 그 때 그 때 구하는 식으로는 시간 초과를 해결할 수 없었다...

문제에 제한값을 사용해 미리 소수를 구하고 그 소수를 찾는 방법을 사용했다.

---

Code

if __name__ == "__main__" :
    
    is_prime = [False, False] + [True] * ((123456 * 2) - 1)
    primes = []
    for i in range(2, int((123456 * 2) + 1)):
        if is_prime[i]:
            primes.append(i)
            for j in range(2 * i, (123456 * 2) + 1, i):
                is_prime[j] = False
    num = int(input())
    while num != 0:
        m_cnt = 0
        for k in primes:
            if num < k <= num * 2:
                m_cnt += 1
            
        print(m_cnt)
        num = int(input())

 

출처

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