백준4948-베르트랑 공준

백준 4948 베르트랑 공준

에라토스테네스의 체는 쉬웠는데 알고리즘 초보자인 나에겐 베르트랑 공준은 너무어려웠다. 2일정도는 머리를 싸매면서 한거같다.
어려웠던 부분은 시간초과가 날 힘들게했고 너무 고민하다보니 아애 갈피가 잡히지 않았다.
분명 에라토스테네스의 체를 통해서 소수를 구해서 에라토스테네스의 체를 이용하면 될거같은데 시간초과가 계속나서 n+1부터 2n까지 모든 수를 소수인지 아닌지를 확인하는 방법도 하였지만 이방법도 시간초과가 났다.

에라토스테네스의 체의 방법으로 소수를 구하는건 맞는데 방식이 잘못되었다.

직접 소수를 구하면 너무 시간이 오래걸린다. 그래서 boolean인 True와 False를 이용해서 소수인수와 소수가 아닌수를 구별해서 풀었다.

while True:
    n = int(input())
    if not 1 <= n <= 123456:
        break;
    allNum2 = [False, False] + [True] * (2 * n - 1)

    pm = 2
    while True:
        for i in range(2, round(2 * n / pm) + 1):
            if pm * i > 2 * n:
                break;
            if allNum2[pm * i] == True:
                allNum2[pm * i] = False
        pm += 1
        if pm * 2 > 2 * n:
            break;
    count = 0
    for i in range(n + 1, 2 * n + 1):
        if allNum2[i] == True:
            count += 1
    print(count)

그런데 이건 매 입력마다 소수를 만들기 때문에(boolean) 처음에 소수한번 만들고 비교하는 식으로 변경했다.

allNum = [False, False] + [True] * (250000)
pm = 2
while True:
    for i in range(2, round(len(allNum) / pm)):
        if pm * i > len(allNum):
            break;
        if allNum[pm * i] == True:
            allNum[pm * i] = False
    pm += 1
    if pm == len(allNum):
        break;

while True:
    n = int(input())
    if n == 0:
        break;
    count = 0
    for i in range(n + 1, 2 * n + 1):
        if allNum[i] == True:
            count += 1
    print(count)