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

문제

베르트랑 공준은 임의의 자연수 n에 대하여

n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

 

 

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

 

 

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

또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

 

 

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

 

---

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 케이스는 n을 포함하며, 한 줄로 이루어져 있다. (n ≤ 123456)

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

 

---

해답을 도출하기 위해서는 먼저 소수를 구하는 방법을 알 필요가 있었습니다.

소수를 구할 수 있는 방법을 위키백과에서 찾아보았습니다.

 

 

링크 : https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0)

 

 

 

 

이전에도 소수와 관련된 문제는 제곱근을 활용하여 해결했기 때문에 이번에도 익숙한 방법으로 진행하였습니다.

 

 

이번 문제에서 까다로웠던 부분은 "시간 초과"입니다.

결과를 도출하는 것까지 수행을 완료했지만 cpu 부담을 최대한 낮추어 경량화할 수 있는 코드가 필요했습니다.

 

 

처음에 진행한 코드는 배열에 소수들을 미리 저장시키지 않고서 즉각적인 계산을 수행하도록 했지만, 정답이 된 코드는 소수들을 미리 구하여 리스트나 튜플에 저장시킨 후 값들을 찾아내야 했습니다.

 

 

처음에는 소수들을 저장하는 리스트 만드는 시간이 더 오래 걸릴 것 같다는 생각을 했지만,

막상 생각해보니 주어진 값만 입력하는 것이 아니라 더욱 다양한 값들을 입력했을 경우에는 즉각적인 연산 방식이 cpu를 기하급수적으로 많이 사용하는 결과를 가져온다는 것을 깨달았습니다.

---

정답 코드

import math

# 소수인지를 판별하는 함수
def checkValue(numValue):
    if numValue == 1:
        return True
    else:
        for comp in range(2, int(math.sqrt(number))+1):
            if numValue % comp == 0:
                return False
    return True


# 소수를 리스트에 저장
value = list(range(123456*2))
prime_number = list()

for number in value:
    if checkValue(number):
        prime_number.append(number)


# 사용자 입력 및 결과 출력
while(1):
    insertN = int(input())
    cnt = 0

    if insertN == 0:
        break

    for valueN in prime_number:
        if insertN < valueN <= insertN*2:
            cnt += 1
    print(cnt)

---

시간 초과 코드

import math

# 소수를 판별하는 함수
def checkValue(numValue):
    if numValue == 1:
        return True
    else:
        for comp in range(2, int(math.sqrt(number))+1):
            if numValue % comp == 0:
                return False
    return True


# 사용자 입력 및 출력 부분
while(1):
    insertN = int(input())
    prime_number = 0
    if insertN == 0:
        break
    else:
        for number in range(insertN+1, insertN*2+1):
            if checkValue(number):
                prime_number += 1
    print(prime_number)

 

 

-끝-