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

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

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보다 작거나 같은 소수의 개수를 출력한다.

최초 접근은 입력 받은 N ~ 2N 까지 매번 소수를 판별하게 구현했다. 당연하게도 시간 초과

import math

def is_Prime(num) :
    for i in range(2, int(math.sqrt(num))+1) :
        if num % i == 0 :
            return False
    return True

while True :  
    count = 0
    N = int(input())
    if N == 0 :
        break
    for i in range(N+1, (2*N+1)) :
        if is_Prime(i) == True :
            count += 1
    print(count)

처음 제출한 코드이다. 매번 입력 값의 범위에서 소수를 판별하니 시간복잡도가 O(n)이다.

해당 문제는 에라토스테네스의 체 알고리즘으로 해결해야 한다.

 

에라토스테네스의 체 알고리즘이란 간단하게 말하면 아래와 같다. (100보다 작은 소수 판별)

1. 숫자 1은 소수도 합성수도 아니니 제거한다.
2. 그 다음 수(2)가 소수이면 자기 자신(2)을 제외한 배수는 모두 제거한다. (2를 제외한 2의 배수 모두 제거)
3. 그 다음 수(3)가 소수이면 자기 자신(3)을 제외한 배수는 모두 제거한다. (3을 제외한 3의 배수 모두 제거)
4. 그 다음 수인 4는 이미 2의 배수라 제거되었으니, 다음으로 가장 작은 소수인 5를 제외한 5의 배수를 제거한다.
5. 마지막으로 5 다음 가장 작은 소수인 7을 제외한 7의 배수를 제거해준다.

5번까지 진행하면 100보다 작은 소수를 구할 수 있다.

 

그럼 왜 7 다음 가장 작은 소수인 11의 배수는 제거하지 않은걸까 의문이 생길 수 있다.

16의 약수는 1, 2, 4, 8, 16이고 4를 기준으로 대칭을 이루고 있다. 즉 16이 2로 나누어 떨어지면 8로도 나누어 떨어진다는걸 알 수 있다. 따라서 임의의 자연수 N이 소수임을 판단하기 위해선 2부터 N의 제곱근까지 나누어 떨어지는지만 확인하면 된다.

 

결론적으로 100의 제곱근은 10이기 때문에 11은 판단하지 않아도 된다.

 

아래는 파이썬으로 구현한 에라토스테네스의 체 알고리즘을 이용해 100보다 작은 소수를 판별하는 코드이다.

import math

N = 100
arr = [i for i in range(N+1)]    # 인덱싱하기 편하게 0부터 생성
arr[1] = 0 	# 1은 소수가 아니기에 0으로 선언
result = []	# 소수를 판별한 후 소수를 담을 리스트

for i in range(2, N+1) :
    if arr[i] != 0 : 	# 0은 소수가 아닌 수. 즉, 소수가 아니라면 for 문을 수행
        for j in range(i*i, N+1, i) : # 자기 자신(소수)을 제외한 자신의 배수는 모두 0
            arr[j] = 0

for i in arr :
    if arr[i] != 0 :
        result.append(arr[i])

print(result)

 

 

정답

import math

num = 123456 * 2 # 입력 받을 값 N의 최대 범위, 아래 while 문에서 for문을 돌 때 N*2만큼 수행하기에 *2 해주었음
arr = [i for i in range(num+1)] # 인덱싱하기 편하게 0부터 배열 생성
arr[1] = 0  # 1은 소수도 합성수도 아니므로 0으로 초기화 (0의 의미는 소수가 아닌 수)

for i in range(2, num+1) :  # 에라토스테네스의 체의 알고리즘을 사용하여 배열을 돌며 소수가 아닌 수는 제거
    if arr[i] == 0 :    # 소수가 아닌 수, 즉 이미 나누어진 수면 수행하지 않음
        continue
    for j in range(i*i, len(arr), i) :  # 소수일 때, 자기 자신을 제외한 배수는 모두 0(소수가 아닌 수)
        arr[j] = 0

while True :
    result = [] # 입력 값의 범위에 속하는 소수를 저장할 리스트
    N = int(input())
    if N == 0 :
        break
    for i in range(N+1, (N*2)+1) :  # N보다 커야하니 N+1부터 수행
        if arr[i] != 0 :
            result.append(arr[i])
    print(len(result))