[백준] 4948번 베르트랑 공준 (Python)

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

 

Source

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

4948번: 베르트랑 공준

 

How to solve?

1929번 문제 풀이 같이 하나하나 대입하여 나누고, 소수인지를 판별하면 시간초과가 발생한다.

따라서 에라토스테네스의 체 원리를 이용하여 문제를 풀이한다.

만약 X를 a*b라고 표현했을 때 X의 제곱근 n에 대하여 a와 b 둘 다 n보다 큰 경우는 없기 때문에

제곱근까지만 판별을 해주면 된다.

이후 파이썬의 리스트 슬라이스 기능을 사용해 n+1에서 2n까지의 True의 갯수를 출력한다.

(리스트 슬라이스는 마지막 값을 미포함하기 때문에 2n+1로 표현)

 

Code

import math
import sys

prime_list = [True] * 246912

for i in range(2, int(math.sqrt(246912))+1):
    if prime_list[i]:
        for j in range(i*2, 246912, i):
            prime_list[j] = False


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

    if n == 0:
        break

    count = prime_list[(n+1):(2*n+1)].count(True)

    print(count)