[백준] 4948번 베르트랑 공준 - 파이썬(Python)

문제 (링크)

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

4948번: 베르트랑 공준

나의 풀이

첫 번째 풀이

 

import sys
import math

data = []

while True:
    n = int(sys.stdin.readline())
# 입력값이 0이 아닐때까지 입력값을 data배열에 저장
    if n == 0:
        break
    else:
        data.append(n)
    
def is_prime_count(x, y): # x이상 y이하의 수 중 소수인 것의 개수 리턴해주는 함수
    arr = [True for _ in range(y+1)]
    arr[1] = False

    for i in range(2, int(math.sqrt(y)) + 1):
        if arr[i]:
            j = 2
            while i * j < y:
                arr[i*j] = False
                j += 1

count = 0
for i in range(x, y):
    if arr[i]:
        count += 1

return count

for x in data:
    print(is_prime_count(x+1, x*2+1)) # x보다 크고 2x보다 작거나 같은 값 사이의 소수의 개수

 

가장 기본적인 에라토스테네스의 체 알고리즘을 이용해 문제를 해결하였다.

 

문제가 n초과 2n이하의 숫자들 사이의 소수의 개수를 출력하는 것이었는데, n이상으로 착각을 해서 계속 실패판정이 났었다.

 

문제를 잘 읽자..

 

위 코드로도 성공을 했지만, 풀고나서 한 가지 생각이 들었다.

 

어차피 arr[i]는 숫자 i가 소수인지 아닌지를 저장해주는 배열인데, 이걸 굳이 매번 함수를 돌릴 때마다 초기화했다가 다시 채워줄게 아니라, 입력 범위 내의 모든 숫자들에 대한 arr[i] 값을 구해놓고 입력값에 대해 갯수만 세면 훨씬 더 효율적일거란 생각이 들었다.

 

따라서 그러한 방식으로도 코드를 작성해봤다.

 

두 번째 풀이

import sys
import math

data = []

while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    else:
        data.append(n)

# 입력 n의 범위는 1 <= n <= 123456 이므로, 2n의 값까지 y를 설정
y = 123456 * 2
arr = [True for _ in range(y+1)]
arr[1] = False

for i in range(2, int(math.sqrt(y))+1):
    if arr[i]:
        j = 2
        while i * j <= y:
            arr[i*j] = False
            j += 1


for x in data:
    count = 0 # data의 각 값들에 대한 count 초기화

    for i in range(x+1, 2*x+1): # x초과 2x이하까지 i가 돈다
        if arr[i]: # arr[i]가 True면 (소수이면)
            count += 1 # 카운트에 1 추가

print(count)

 

입력값으로 들어오는 n 은 1 이상 123456 이하이므로, 최대 범위가 될 수 있는 값은 2n일 경우의 123456 * 2이다.

 

따라서, arr를 123456 * 2의 범위만큼 설정해주고 소수 여부를 처리해줬다.

 

이후, data의 값들을 돌면서 x 초과 2x 이하에 대한 count를 계산해주는 방식을 거쳤다.

 

 

 

 

위에 것의 두 번째 풀이, 밑에 것이 첫 번째 풀이

 

두 풀이 모두 통과판정을 받았지만, 걸린 시간 차이가 6배로, 엄청난 시간적 차이를 보였다.