백준 4948, 베르트랑 공준, python

문제

베르트랑 공준은 임의의 자연수 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

 

 문제풀이

N이 주어지면 N과 2N 사이에 소수가 있다면, 소수 개수를 세어 출력으로 내어주면 된다. 소수를 판별하는 코드는 외우다시피 하고있어서, 그 동안 풀어왔던 방법대로 풀어보았다.

# 베르트랑 공준
import sys
input = sys.stdin.readline

n = int(input())

while n != 0:
    sosu = 0
    
    # n 보다 크고 2n 보다 작거나 같음
    for i in range(n+1, 2*n +1):
    	
        # 소수 판별
        for j in range(2, int(i**0.5) + 1):
        	# 소수는 1과 자신으로만 나뉘어지는 수 이므로,
            # 만약 1과 자신 외에 나눠지는 경우가 있으면 소수가 아니므로 break
            if i % j == 0:
                break
        # for문을 break 없이 다 돌았다면 소수이므로 1 카운트
        else:
            sosu += 1
    
    # 소수 개수 출력
    print(sosu)
	
    # 다시 while 문을 돌기 위한 n 값을 받는다
    n = int(input())

 

위 코드는 시간복잡도 O(N ** 0.5) 임에도 제출 시, 시간초과가 발생했다. 시간복잡도를 더 줄이기 위해, 구글링을 해본 결과 에라토스테네스의 체를 사용하여 시간 복잡도를 O(NlogN)으로 줄일 수 있다고 한다. 

 

 

에라토스테네의스 체란?

수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 그의 소수를 판별하는 알고리즘은 다음과 같다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

그림의 경우, {\displaystyle 11^{2}>120}

이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

출처 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

위 출처 사이트를 방문하면 위 알고리즘이 어떠한 식으로 작동하는지 시각적으로 볼 수 있다.

 

에라토스테네스의 체를 파이썬으로 구현한 코드는 다음과 같다.

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

즉, sieve 라는 리스트에 n개 만큼 true 넣어주고 각 값이 소수라면 true, 아니면 false 를 저장해두고 소수를 판별할 때 해당하는 숫자가 true 이면 별도의 계산 없이 바로 소수 판별이 가능하다.

 

어쨌든, 미리 소수를 판별해 놓은 리스트를 사용하여 n과 2*n 사이에 소수가 있으면 별도의 계산 없이 소수 갯수를 세어주기만하면 된다는 뜻이다. 수정한 코드는 다음과 같다

# 베르트랑 공준
import sys
input = sys.stdin.readline

# 소수를 판별하는 함수
def sosu(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

# 가능한 숫자의 범위
num_list = list(range(2, 246912))
sosu_list = []

# sosu_list 에 소수인 숫자를 넣는다
for i in num_list:
    if sosu(i):
        sosu_list.append(i)

n = int(input())
while n != 0:
    cnt = 0
    
    # 미리 만들어놓은 sosu_list에서 소수의 개수를 세어준다
    for i in sosu_list:
        if n < i <= 2*n :
            cnt += 1
    
    # 소수 개수 출력
    print(cnt)
    
    # while문을 반복하기 위한 n값 다시 받기
    n = int(input())

시간복잡도 관련하여 공부가 많이 필요한 것 같다. 매번 생각 없이 코드를 작성하곤 하는데.. 계속 이렇게 생각없이 코드 작성하다간 다...죽어!!!