파이썬으로 풀어보는 백준 4948번: 베르트랑 공준

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

4948번: 베르트랑 공준

 

내 풀이:

n=int(input())
while n!=0:
    arr = [False, False] + [True] * (2*n-1)
    for i in range(2, int((2*n+1)**0.5+1)):
        if arr[i]:
            for j in range(i * 2, len(arr), i):
                arr[j] = False
    result=0
    for k in range(n+1,2*n+1):
        result+=arr[k]
    print(result)
    n = int(input())

2672ms

나름 최적화하여 문제를 풀기 위해 while문으로 각 경우에 따른 최소의 소수범위를 구했는데 이때문에 샘플 문제가 많이질수록, 또 샘플 문제가 필요로 하는 소수 범위가 클수록 시간이 기하급수적으로 커진다.

 

asm9677님 풀이:

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]]
 
def Search(prime, n):
    l,r = 0, len(prime)-1
    while l<=r:
        m=(l+r)//2
 
        if prime[m] > n:
            r = m-1
        else:
            l = m+1
    return l
 
prime = GetPrime(123456*2)
while True:
    n=int(input())
    if n==0:
        break
    print(Search(prime, n*2) - Search(prime, n))