백준4948 - 베르트랑 공준 (에라토스테네스의 체) Python

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

해당 문제는 입력값이 1 <= n <= 123456 사이로 주어질 때,

n + 1이상, 2n 이하 사이에 존재하는 모든 소수의 갯수를 반환하는 문제다.

 

이를 풀이하기 위해 소수를 찾는 알고리즘 중 하나인 에라토스테네스의 체를 활용했는데, 해당 알고리즘 동작 방식은 아래와 같다.

1. 먼저 소수를 판별하기를 원하는 수만큼의 공간을 가진 리스트를 생성하고 모든 수가 소수(True)라고 가정한다. 

(해당 문제에서는 n의 최댓값이 123456이고, 2n은 123456 * 2 이므로 123456 * 2 + 1 길이를 가진 리스트 생성)

2. 기본적으로 소수가 아닌 0과 1을 비소수(False)로 설정한 뒤, 2부터 시작하여 숫자를 살핀다.

3. 만약 소수인 경우, 해당 수의 배수를 모두 비소수로 설정한다. (123456 * 2 + 1 이하의 수)

4. 위 과정이 진행되었다면, 다시 2번으로 돌아가 진행을 반복한다.

 

에라스토테네스의 체를 소스 코드로 표현하면 다음과 같다.

def makingTable () :
  n = 123456 * 2 + 1
  table = [True] * n
  table[0] = table[1] = False

  i = 2
  while (i**2 <= n) :
    if table[i] :
      for j in range(i**2, n, i) :
        table[j] = False
    i += 1
  return table

 

에레스토테네스의 체를 활용하여 소수판별이 끝났다면,

입력값이 들어온 경우 n + 1 과 2n + 1 사이의 값 중에서 소수의 갯수를 세어 반환하면 되는데

이는 다음과 같이 작성했다.

def countPrimes (table,n) :
  return str(table[n+1:2*n+1].count(True))
  # 컴프리헨션을 활용하여
  # return [v for v in table[n+1:2*n+1] if v] 로도 작성 가능

 

전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()

def solution (data) :
  data.pop()
  table = makingTable()
  result = list(map(lambda x : countPrimes(table,int(x)), data))
  print('\n'.join(result))

# 에리스토테네스의 체
def makingTable () :
  n = 123456 * 2 + 1
  table = [True] * n
  table[0] = table[1] = False

  i = 2
  while (i**2 <= n) :
    if table[i] :
      for j in range(i**2, n, i) :
        table[j] = False
    i += 1
  return table

def countPrimes (table,n) :
  return str(table[n+1:2*n+1].count(True))

solution(input_data)