[단계별로 풀어보기] [python3] 기본 수학 2 - 베르트랑 공준 (4948)

4948번: 베르트랑 공준 (acmicpc.net)

4948번: 베르트랑 공준

첫 제출

def isSo(k):
    isTrue = [True]*(k*2)
    for i in range(2, k*2):
        for j in range(i-1, k*2, i):
            isTrue[j] = False
    count = 0

    for i in range(k-1, k*2):
        if isTrue[i] == True:
            count += 1
    print(count)

n = int(input())
tc = []
while n != 0:
    tc.append(n)
    n = int(input())

for t in tc:
    isSo(t)

시간복잡도가 O(n^3)이므로 시간초과로 실패함.

에라토스테네스의 체와 소수 판별을 분리시켜서 해결했다.

최종 제출

def eratos(num):
    isTrue = [True]*(num*2)
    isTrue[0] = False
    for i in range(2, num*2):
        for j in range(i, num*2, i):
            if i==j:
                continue
            isTrue[j-1] = False
    isTrue[(num*2)-1] = False
    return isTrue
            
def isSo(k, era):
    count = 0
    for i in range(k, k*2):
        if era[i] == True:
            count += 1
    print(count)

n = int(input())
tc = []
while n != 0:
    tc.append(n)
    n = int(input())
era = eratos(max(tc))

for i in tc:
    isSo(i, era)