[백준알고리즘 - 4948] 베르트랑 공준 (Python)

(1) 문제

• 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.
• 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.
• 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)
• 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 

 

---

(2) 입력

• 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.
• 입력의 마지막에는 0이 주어진다.
• 1 ≤ n ≤ 123,456

 

---

(3) 출력

• 각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

 

---

(4) 예제 입력 및 출력

---

(5) 코드

• n이 123456 이하로 제한되어 있어 소수를 미리 구하고 비교

import sys
import math

prime = []

for i in range(2, (123456 * 2) + 1):
    prime_check = True
    #제곱근 구하기
    sqrt_number = int(math.sqrt(i + 1))
    for j in range(2, sqrt_number + 1):
        if i % j == 0:
            prime_check = False
            break
    if prime_check:
        prime.append(i)

while True:
    number = int(sys.stdin.readline())
    count = 0
    if number == 0:
        break

    for element in prime:
        if element > number:
            if element <= number * 2:
                count += 1
            else:
                break
    
    print(count)

 

• 글자수 사이의 소수를 실시간으로 구하기(python3로 하면 시간초과 pypy통과)

import math
import sys

while True:
    number = int(sys.stdin.readline())
    if number == 0:
        break
    min_number = number + 1
    max_number = number * 2

    prim_count = 0

    for i in range(min_number, max_number + 1):
        prime_check = True
        #제곱근 구하기
        sqrt_number = int(math.sqrt(i + 1))
        for j in range(2, sqrt_number + 1):
            if i % j == 0:
                prime_check = False
                break
        if prime_check:
            prim_count += 1

    print(prim_count)

---

(6) 실행결과

---