백준 4948번: 베르트랑 공준 (S2) - Python 풀이

문제 설명

https://www.acmicpc.net/problem/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

1
10
13
100
1000
10000
100000
0

예제 출력 1

1
4
3
21
135
1033
8392

문제 요약) n보다 크고, 2n보다 작거나 같은 소수 개수 출력해라. n으로 0 들어오면 프로그램 종료.

풀이 과정

2022년 11월 15일의 나야 안녕? 휴학 중인데도 장하구나. 과거에도 시간 초과 경험 후 맞았더랍니다.

소수 찾을 때는 뭐 쓴다? 에라토스테네스의 체~를 씁니다.

에라토스테네스의 체

• 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법입니다.
• 로직
  1. 1은 소수가 아니니까 제거
  2. 지워지지 않은 수 중 제일 작은 수를 소수로 채택 (ex. 2)
  3. 범위 내에서 이 수의 배수를 모두 제거
  4. 다 확인할 때까지 2번과 3번을 반복
  5. 최종적으로 남아있는 숫자가 범위 내의 소수

이것을 사용해 소수를 구하면 됩니다.

처음에 시간 초과가 났던 이유는 n을 입력 받을 때마다 위의 짓을 해서인데, 입력의 최댓값인 123456 범위 내에서 위의 짓을 최초 1번만 하면 어떤 n이 들어와도 답을 출력할 수 있습니다. 배열 슬라이싱을 통해 n과 2n 사이의 값을 가져와서 소수의 개수를 출력하면 됩니다.

정답 코드

# n의 최댓값을 기준으로 가능한 모든 범위의 소수 찾기를 진행
max_value = 123456
# 0과 1은 소수가 아니라서 False, 그 뒤는 일단 모두 True로 초기화
is_prime_arr = [False, False] + [True] * (2*max_value-1) 

# 0과 1은 볼 필요 없기 때문에 2부터 시작하고
# 최대 범위인 2*n까지 확인
for i in range(2, 2*max_value+1):
    # i의 첫 번째 배수 = 2 * i부터 최대 범위까지 i만큼 점프하며 i의 모든 배수를 확인
    for j in range(2*i, 2*max_value+1, i):
        # 소수면
        if is_prime_arr[j]:
            # 제거
            is_prime_arr[j] = False

# 입력 받기 시작
while True:
    n = int(input())
    # 0이면 프로그램 종료
    if n == 0: break
    # n+1부터 2n까지 배열에서 소수의 개수를 출력
    print(is_prime_arr[n+1:2*n+1].count(True))

Bool 타입 배열을 사용해 소수면 True, 소수가 아니면 False로 저장했습니다.

이상입니다.