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

문제

www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

 

풀이

에라토스테네스의 체를 이용하여 풀었다. 입력의 한계를 고려하여 사용했던 숫자를 기록해둔 후에 중복 계산을 피하는 방식으로 최적화를 했다. 하지만, 먼저 모든 해를 구한 것과 시간 차이는 그리 크지 않았다(30ms). 

https://wikidocs.net/21638

코드

1번 풀이

N = 123456
max_num = 0
isPrime = [False, False] + [True]*(2*N - 1)

def count_num(n):
    global max_num
    if max_num < n:
        for i in range(max_num*2 + 1, 2*n + 1): # max_num*2까지는 계산이 되었으므로
            if isPrime[i]:
                for j in range(2*i, 2*N + 1, i):
                    isPrime[j] = False
        max_num = n
        return isPrime[n+1:2*n + 1].count(True)
    else:
        return isPrime[n+1:2*n + 1].count(True)


while True:
    n = int(input())
    if n:
        print(count_num(n))
    else:
        break

2번 풀이

N = 123456
max_num = 0
isPrime = [False, False] + [True]*(2*N - 1)

for i in range(2, 2*N + 1): # max_num*2까지는 계산이 되었으므로
    if isPrime[i]:
        for j in range(2*i, 2*N + 1, i):
            isPrime[j] = False

while True:
    n = int(input())
    if n:
        print(isPrime[n+1:2*n + 1].count(True))
    else:
        break