[kata][python] 베르트랑 공준(feat. 에라토스테네스의 체)

베르트랑 공준(Bertrand’s postulate)

출처: 백준 알고리즘 4948번 문제

베르트랑 공준은 임의의 자연수 n에 대해,

n보다 크고 2n보다 작거나 같은 소수가 적어도 하나 존재한다는 내용을 담고있다.

이에 근거해서 입력으로 n이 주어졌을 때,

n보다 크고 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하라.

입력
    1
    10
    13
    100
    1000
    10000
    100000
    0

출력
    1
    4
    3
    21
    135
    1033
    8392

내 풀이1 (시간 초과)

  1 import sys
  2 import math
  3
  4 def is_prime(n):
  5     if n == 2:
  6         return True
  7
  8     if n % 2 == 0:
  9          return False
 10
 11     for i in range(3, int(math.sqrt(n)) + 1, 2):
 12         if n % i == 0:
 13             return False
 14
 15     return True
 16
 17
 18 while True:
 19     n = int(sys.stdin.readline())
 20
 21     if n == 0:
 22         break
 23
 24     prime_cnt = 0
 25
 26     for i in range(n+1, (2*n)+1):
 27         if is_prime(i):
 28             prime_cnt += 1
 29
 30     print(prime_cnt)

(26~28) 입력받은 n에 대해 n부터 2n까지 iteration을 돌며 소수를 체크했다.

(5~6) 2는 짝수중 유일한 소수이므로 예외적으로 True를 리턴했다.

(8~9) 2를 제외한 나머지 짝수는 소수가 아니므로 False를 리턴했다.

(11) 특정 수가 약수를 가졌는지 판단하기 위해서는 해당 수의 제곱근까지만 판단하면 되기때문에 math.sqrt를 적용했다.

(11~13) 나누어 떨어진다면 소수가 아니므로 False를 리턴했다.

(15)그 이외의 경우는 모두 True를 리턴했다.

내 풀이2 (정답)

  1 import sys
  2 import math
  3
  4 limit = 123456
  5
  6 eratos = [1] * (2 * limit + 1)
  7 eratos[0] = 0
  8 eratos[1] = 0
  9
 10 for i in range(2, int(math.sqrt(len(eratos)))):
 11     if eratos[i]:
 12         for j in range(i + i, len(eratos), i):
 13             eratos[j] = 0
 14
 15 while True:
 16     n = int(sys.stdin.readline())
 17
 18     if n == 0:
 19         break
 20     else:
 21         print(sum(eratos[n+1:(2*n)+1]))

에라토스테네스의 체를 활용했다.

용어는 거창하지만,

그냥 2부터 시작해서 배수를 구하고, 그 배수를 소수에서 제외하는 방식이다.

특정 수의 배수라는 것은 소수가 아니라는 뜻이기 때문이다.

2를 제외한 2의 배수를 구해서 전부 지운다.

3을 제외한 3의 배수를 구해서 전부 지운다.

4는 체크할 필요 없다. 2의 배수를 구할때 이미 체크했다.

5를 제외한 5의 배수를 구해서 전부 지운다.

…

n의 제곱근보다 큰 정수중 가장 작은 정수까지 이것을 반복하면 된다.

예를들어 120이하의 소수를 구할 경우, 120이 아닌 11까지만 반복해주면 된다.

120의 제곱근보다 큰 정수중 가장 작은 정수가 11이기 때문이다.

어쨌든 이렇게 일일이 배수를 구해서 지우는 좀 단순 무식한(?) 방법이다.

특정 숫자 길이만큼 1이 담긴 리스트를 만들고, 소수가 아닌 것은 0으로 체크한다.

(4) 문제에 123456 이하의 숫자가 입력 될 것이라고 했으므로, limit를 123456으로 설정했다.

(6) n부터 2n까지 계산을 해야하므로 limit의 2배 길이 리스트를 미리 생성하고 전부 1로 초기화했다.

(6) +1을 더해준 이유는 인덱스번호가 0부터 시작하기때문에 편의상 인덱스 번호와 실제 숫자를 맞춰주기 위함이다.

(7~8) 0과 1은 소수가 아니므로 미리 0으로 체크해준다.

(10~13) 2부터 전체 길이의 제곱근만큼 iteration을 돌며, 각 숫자의 배수를 전부 0으로 체크했다.

(21) 미리 구해놓은 리스트에서 n보다 크고 2n보다 작거나 같은 소수의 갯수를 구해 출력한다.

분석

첫 번째 시도에서 예제에 있는 정답도 제대로 나오고 시간이 그렇게 오래 걸리는 것 같지 않았는데,

답안을 제출해보니 시간초과가 발생했다.

제곱근까지 비교를 한다거나 짝수를 제외하는 등,

나름 최선을 다했는데도 시간초과가 나서 멘붕이 왔다.

구글링을 해보니 에라토스테네스의 체 라는 개념이 있었다.

용어에 압도되어서 쫄았는데, 내용을 보니 별거 아니었다.

그냥 특정 수의 제곱근보다 작은 정수의 배수를 계속 구하면서 소수에서 제외시키는 방식이었다.

소수를 다루는 문제는 어찌보면 상당히 단순하면서도 풀때마다 새로운 개념이 등장해서 재밌는 것 같다.

코딩장이

-장이: [접사] ‘그것과 관련된 기술을 가진 사람’의 뜻을 더하는 접미사.

Share Share