21/01/09 TL. 백준 4948

오늘 할 일

인프라 엔지니어 교과서 10 ~ 11

개발자를 위한 윈도우 셋업 #3~4

파이썬 알고리즘 #2-1~3

 

매일 할 일

백준 알고리즘 풀이, 검토

---

백준 4948번 : 베르트랑 공준

 

내 풀이

def run():
    ber = bertrand(123456)
    num = int(input())
    while num != 0:
        result = [i for i in range(num + 1, num * 2 + 1) if ber[i] == True]
        print(len(result))
        num = int(input())


def bertrand(num):
    ber = [True] * (2 * num + 1)
    ber[0], ber[1] = False, False

    for i in range(2, len(ber)):
        for j in range(i+i, len(ber), i):
            ber[j] = False
    return ber


if __name__ == "__main__":
    run()

 

에라토스테네스의 체를 이용해서 풀었다. 소수의 개수를 매번 계산하면 효율이 떨어지므로, 미리 입력에 들어갈 수에 해당하는 123456개의 소수 수를 미리 구해놓은 후 개수만 구하는 식으로 문제를 풀었다. 아쉬운 점이 있다면, betrand()에서 반복문을len(bar)만큼 반복하는데, 이럴 필요가 없는 게 (tmp = 2*num+1)의 최대 약수는 sqrt(tmp)일 것이다 따라서, tmp = int(2*num+1)을 추가해 주고, for i in range(2, tmp)로 했으면 성능이 더 향상됐을 것 같다.

 

다른 사람 풀이

import bisect
def GetPrime(n):
    if n < 2:
        return []
    n += 1
    save = [1] * (n // 2)
    for i in range(3, int(n ** 0.5) + 1, 2):
        if save[i // 2]:
            k = i * i
            save[k // 2::i] = [0] * ((n - k - 1) // (2 * i) + 1)
    return [2] + [(2 * i + 1) for i in range(1, n // 2) if save[i]]

prime = GetPrime(123456*2)
while True:
    n=int(input())
    if n==0:
        break
    print(bisect.bisect_right(prime, 2 * n) - bisect.bisect_right(prime, n))

이 사람도 save에 sqrt한 만큼만 넣어서 효율을 끌어올렸다. 그리고, 홀수만 검색하려고 2마다 검색을 한 것 같다.

bisect : 정렬된 순서를 유지한 채 삽입할 수 있다.

bisect_right(a, x) : 정렬돼있는 a에 x가 들어갈 위치(오른쪽에서부터) 리턴