[백준 코딩테스트(Python)] 기본 수학 2 - 베르트랑 공준

4948번: 베르트랑 공준

---

문제

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 

 

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0이 주어진다.

 

출력

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

 

제한

1 ≤ n ≤ 123,456

 

---

1. 문제 접근 방식

n보다 크고 2n보다 작거나 같은 범위에 있는 소수의 갯수를 구하는 문제이다.

① 우선 2부터 2n까지의 구간에서 소수를 찾아 sosu 리스트에 추가한다.

② 주어진 n으로 n보다 크고 2n보다 작거나 같은 범위에 해당되는 소수들을 sosu 리스트에서 찾아서 갯수를 세어준다.

 

① 소수 구하기

주어진 범위 (1 ≤ n ≤ 123,456)를 활용하여 2n까지의 값을 lst에 담아보자.

그리고 lst에 담긴 수 모두를 for 반복문을 통해서 소수인지 확인해보자. 소수인지 판단하는 함수는 '에라토스테네스의 체' 알고리즘을 활용하여 만들면 된다. 

 

✔ 소수인지 판단하는 함수

- 에라토스테네스의 체 알고리즘을 활용하여 입력값의 제곱근까지의 구간에서 약수가 있는지 확인하여 소수인지 판단함

- 소수이면 True, 소수가 아니면 False를 출력하도록 함수를 만듦

## 소수인지 판단하는 함수
def check_sosu(x):
    # 1은 모든 수의 약수이므로 False
    if x == 1:
        return False
    # 2~제곱근 수까지 약수가 있으면 False
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    # 이외에는 소수
    return True

  

✔ 함수를 활용하여 소수 구하기

## 소수 구하기 (위의 함수를 활용)
lst = list(range(2, 2*123456))  # 문제에서 제한한 범위
sosu = []  # 판단한 소수를 담는 리스트

# 2부터 2n까지의 수가 담긴 lst에서 수를 하나씩 꺼내 소수인지 확인
# 소수가 맞으면 sosu 리스트에 추가
for num in lst:
    if check_sosu(num):
        sosu.append(num)

 

② 범위 내에 있는 소수 갯수 구하기

이번 문제에서는 새로운 입력 방식이 나왔다. 하나의 수를 입력하고 0을 입력하면 종료되는 것으로 입력이 끝난다.

이것은 while문을 활용하면 된다.

 

위에서 소수를 담은 sosu 리스트에서 수를 하나씩 꺼내어 n보다 크고 2n보다 작거나 같은 경우에 count에 1을 더한다. 하나의 입력 값에서의 소수의 갯수를 구하는 것이기 때문에 while문 안에서 코드가 작동해야 한다.

 

## 입력 및 출력
while True:
    n = int(input())
    if n == 0:
        break
    
    # sosu 리스트에서 수를 하나씩 꺼내 n보다 크고 2n보다 작거나 같으면 count에 1 더함
    count = 0
    for s in sosu:
        if n < s <= n*2:
            count += 1
    print(count)

 

 

2. 풀이 코드

## 소수인지 판단하는 함수
def check_sosu(x):
    if x == 1:
        return False
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True

## 소수 구하기 (위의 함수를 활용)
lst = list(range(2, 2*123456))
sosu = []

# 2부터 2n까지의 수가 담긴 lst에서 수를 하나씩 꺼내 소수인지 확인
for num in lst:
    if check_sosu(num):
        sosu.append(num)

## 입력 및 출력
while True:
    n = int(input())
    if n == 0:
        break
    
    # sosu 리스트에서 수를 하나씩 꺼내 n보다 크고 2n보다 작거나 같으면 count에 1 더함
    count = 0
    for s in sosu:
        if n < s <= n*2:
            count += 1
    print(count)

 

시간 초과 코드

내가 작성한 코드는 하나의 입력값에 대한 구간 내에 있는 수들을 하나씩 비교해가기 때문에 시간초과로 뜬 것 같다.

while True:
    n = int(input())

    if n == 0:
        break
    
    cnt = 0

    for i in range(n+1, 2*n+1):
        if i == 1:
            continue
        elif i == 2:
            cnt += 1
        else:
            for j in range(2, int(i**0.5)+1):
                if i % j == 0:
                    break
            else:
                cnt += 1
    print(cnt)

 

3. 참고 코드

백준 파이썬 4948: 베르트랑 공준

 

백준 4948(베르트랑 공준) 파이썬(python) 해결