[BOJ] 백준 4948 베르트랑 공준 Python

 

문제

• 4948 베르트랑 공준
• 베르트랑 공준: 임의의 자연수 n에 대해 n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 명제

입력

• 여러 개의 자연수 n

출력

• n < x <= 2n인 x 중 소수의 개수 구하기

제한

• 1 <= n <= 123456

 

---

 

1️⃣ 코드 (오답)

import math

# 소수면 true인 배열 만들기
arr = [True for _ in range(0,123456 * 2 + 1)]

arr[0] = arr[1] = False

for i in range(2, 123456*2+1):
    if i%2==0:
        arr[i] = False
    if i==2:
        arr[i] = True
    
    for j in range(3, int(math.sqrt(i))+1):
        if i%j==0:
            arr[i] = False

# 소수의 개수 출력하기
while True:
    n = int(input())
    if n == 0:
        break
    
    count = 0
    for i in range(n+1, 2*n+1):
        if arr[i]:
            count += 1
    
    print(count)

 

1차원 array에 123456 * 2까지 소수면 True, 소수가 아니면 False를 저장하려 했다. 그래서 우선 True로 초기화된 1차원 arr를 만들고, 소수면 True를 저장하는 이중 for문을 만들었다. 그 후 input을 사용해 입력을 받고 for문을 사용해 True의 개수를 세는 방법으로 코드를 작성했으나 시간 초과로 인해 문제를 틀렸다. 에라토스테네스의 체를 사용하지 않고 문제를 풀어보고 싶었으나 1초라는 시간제한에 걸렸다. 그래서 에라토스테네스의 체 방법을 사용해 다시 문제를 풀었다.

 

2️⃣ 코드 (정답)

import math

MAX_NUMBER = 123456*2

# 소수면 true인 배열 만들기
arr = [True for _ in range(0, MAX_NUMBER + 1)]

arr[0] = arr[1] = False

for i in range(2, int(math.sqrt(MAX_NUMBER)) + 1):  
    if arr[i]: 
        for j in range(i * i, MAX_NUMBER + 1, i):  # i의 배수들을 모두 제거
            arr[j] = False

# 소수의 개수 출력하기
while True:
    n = int(input())
    if n == 0:
        break
    
    print(sum(arr[n+1:2*n+1]))

 

• 개선한 점
  • 에라토스테네스의 체 활용
    • 기존 코드는 각 숫자마다 소수 여부를 판별하여 O(N√N)의 시간 복잡도를 가졌다.
    • 개선한 코드는 `i * i` 를 통해 배수들을 한 번에 제거하여 O(N log log N)의 시간 복잡도를 가져 이전 코드보다 빠르게 동작한다.
  • 코드의 성능을 저하하는 불필요한 연산 제거
    • 불필요한 if문들을 없애고, for문의 범위를 2부터 시작했다. (기존엔 if문으로 2를 따로 판별하고 3부터 시작)
    • for문이 반복되는 범위를 i의 배수로 설정하여 1씩 증가하는 for문보다 빠르게 동작한다.
  • 소수 개수 출력 시 for문 대신 배열의 인덱스를 통한 부분 슬라이싱 활용
    • n+1부터 2n까지
    • True는 1, False는 0이기 때문에 sum 함수를 사용한다면 True의 개수만 구할 수 있다.

 

자료구조 

• 1차원 리스트 arr: arr[i]가 True면 소수, False면 합성수
• 정수 n: 입력받은 값

공간 복잡도

• 1차원 리스트 arr: O(N)
• 정수 n: O(1)

시간 복잡도

• 첫 번째 for문: O(√N)
  • i는 2부터 √MAX_NUMBER까지 반복
• 두 번째 for문: O(N log log N) 
  • i의 배수를 제거하는 반복문으로 N개의 숫자 중에서 각 숫자의 배수를 지우는 시간은 O(log log N)
  • 총 N개의 숫자를 가지기 때문에 O(N log log N)의 시간 복잡도를 가짐