파이썬 베르트랑 공준(백준BOJ 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
📝 풀어보기
이 문제를 풀면서 기존에 알고있던 에라토스테네스의 체 방법을 잘못 구현하고 있었다는것을 깨달았다.
먼저 기존의 코드를 보자.
기존 코드
import sys
M, N = map(int, sys.stdin.readline().split())
# 에라토스테네스의 체 방식 사용
for i in range(2, N+1): # 2부터 N+1의 범위까지 탐색
check = True
for j in range(2, int(i**0.5)+1): # 2부터 i의 제곱근까지만 수행
if i % j == 0: # 소수가 아닐 경우
check = False
break
if check: # 소수일경우
if i >= M: # M 이상의 소수만 추가
print(i)
나는 처음 베르트랑 공준 문제를 접했을때 여기서 2N의 범위 내에서 소수를 구하게끔 바꾸기만 하면 된다고 생각했다. 하지만 이 문제의 요점은 제한시간과 제한값에 있었다.
이전에 짠 이 코드는 케이스마다 입력한 수를 구하고, 소수를 판별하고, 답을 내놓는다.** 하지만 이 방법으로는 처리시간이 요구시간에는 절대 미치지 못한다.
📌 일단 이 문제에는 1 ≤ n ≤ 123,456 라는 제한이 걸려있다.
즉, 최대값(m)은 123,456이다.
소수 판별을 위해 먼저 리스트를 생성하고 2*m+1 의 범위에서 소수인 경우 리스트에 저장되도록 했다. 0 과 1 은 소수가 아니므로 판별 전 미리 False로 지정했다.
m = 123456 # 문제에서 제시한 최대값
array1 = [] #소수 판별을 위한 리스트설정(True면 소수)
for _ in range((2*m)+1):
if True:
array1.append(_)
array1[0], array1[1] = False, False #0,1은 소수가 아니기에 False로 설정
📌 에라토스테네스의 체 공식을 사용한다. 2부터 2*m의 제곱근까지 범위에서 i가 True인 경우에 j = 2로 하고 2*m 보다 작을 동안 i와 j를 곱해나간다. 그렇다면 출력은 2 4 6 8…m, 6, 9, 12..m, 4(2의 배수이므로 생략), 5 10 15..m이 될것이다.
이렇게 나온 i*j 값은 모두 소수가 아니므로 리스트에서 전부 False로 바꾼다.
여기까지 계산한것을 메모리에 올린다.
# 에라토스테네스의 체 공식
for i in range(2, int((2*m)**0.5)+1): # 2부터 2*m의 제곱근 까지
if array1[i]: #만약 array1[i]가 True라면
j = 2 # i에 곱해줄 j값을 2부터 설정
while i*j <= (2*m): #i * j 가 (2*m) 보다 작거나 같을때 까지 구한다.
array1[i * j] = False # 2 4 6 8...m, 6 9 12...m.. 5 10 15..m
j += 1 # 해당 i*j의 값은 소수가 아니므로 False로 설정
📌 여기서부터 입력값이다.
입력할 변수 n과 cnt를 선언하고 0을 입력하면 반복문에서 탈출되도록 한다.
제시된 조건에서 n보다 크고 2n보다 작아야 하기때문에 n+1에서 2*n+1 범위에서 리스트 안에 True를 만날 경우 cnt를 증가시킨다.
그리고 증가된 값을 출력한다.
while True:
n = int(input())
if n == 0: #0이면 반복문 탈출
break
cnt = 0
# 개수 출력
for i in range(n+1, (2*n)+1): #n+1(n보다 커야하기 때문) 부터 2 * n + 1 까지 설정
if array1[i]: #만약 해당 i가 True(소수) 라면
cnt += 1 #count값에다 +1
print(cnt) #count 값 출력
변경 후 코드
m = 123456 # 문제에서 제시한 최대값
array1 = [] #소수 판별을 위한 리스트설정(True면 소수)
for _ in range((2*m)+1):
if True:
array1.append(_)
array1[0], array1[1] = False, False #0,1은 소수가 아니기에 False로 설정
# 에라토스테네스의 체 공식
for i in range(2, int((2*m)**0.5)+1): # 2부터 2*m의 제곱근 까지
if array1[i]: #만약 array1[i]가 True(소수)라면
j = 2 # i에 곱해줄 j값을 2부터 설정
while i*j <= (2*m): #i * j 가 (2*m) 보다 작거나 같을때 까지 구한다.
array1[i * j] = False # 2 4 6 8...m, 6 9 12...m.. 5 10 15..m
j += 1 # 해당 i*j의 값은 소수가 아니므로 False로 설정
while True:
n = int(input())
if n == 0: #0이면 반복문 탈출
break
count = 0
# 개수 출력
for i in range(n+1, (2*n)+1): #n+1(n보다 커야하기 때문) 부터 2 * n + 1 까지 설정
if array1[i]: #만약 해당 i가 True(소수) 라면
count += 1 #count값에다 +1
print(count) #count 값 출력