[백준] 4948. 베르트랑 공준

4948번: 베르트랑 공준

---

처음에 이렇게 풀었는데 시간 초과가 났다

# 4948 베르트랑 공준
import math

def isPrime(n):
    cnt = 0
    for num in range(n + 1, 2 * n + 1):
        sq = int(math.sqrt(num))
        flag = False
        for i in range(2, sq+1):
            if num % i == 0:
                flag = True
                break

        if flag is True:
            continue
        else:
            cnt += 1
    return cnt

arr = []
while True:
    N = int(input())
    if N == 0:
        break
    arr.append(N)

for n in arr:
    if n == 0:
        break
    else:
        print(isPrime(n))

그래서 계속 방법을 고민했는데, 도저히 모르겠어서 블로그 글을 참조하고 깨달았다.
아 이건... 파이썬이 잘못한거다...ㅋㅋㅋㅋ 파이썬이 인터프리터 언어라 컴퓨터가 한 줄씩 기계어로 해석하며 실행시켜야 하므로 자바나 C에서 같은 알고리즘을 적용했을 때와 달리 시간 초과가 날 수밖에 없는 것이었다.

그래서 아래 블로그의 해법을 참고해, 1부터 입력값의 최대값인 123456의 2배까지 모든 수가 소수인지를 미리 따져서 리스트에 넣어두고, 숫자가 주어지면 리스트에서 해당 인덱스 범위 내의 소수를 찾는 방식으로 문제를 풀 수 있었다.

[ 백준 알고리즘 ] 4948번 베르트랑 공준 (JAVA/python)

# 4948 베르트랑 공준 1628ms
# 미리 소수인지 여부 넣어두기
max_num = 123456 * 2 + 1
num_list = [False for _ in range(123456 * 2 + 1)]

for i in range(2, max_num):
    flag = False
    sq = int(i ** 0.5)
    for z in range(2, sq + 1):
        if i % z == 0:
            flag = True
            break

    if not flag:
        num_list[i] = True

# 숫자 받아서 해당 숫자 초과, 2배 이하인 범위의
# True인 숫자 cnt 세기
arr = []

while True:
    N = int(input())
    if N == 0:
        break
    arr.append(N)

for a in arr:
    cnt = 0
    for b in range(a+1, 2*a+1):
        if num_list[b]:
            cnt += 1
    print(cnt)

 이렇게 했더니, 내가 이제껏 풀었던 소수 문제들 중 가장 시간이 적게 들었다.
미리 소수인지 여부를 찾아놓고 푸는 방법이 반복문을 돌리며 매번 함수를 실행시키는 것보다 확실히 시간을 단축시킬 수 있다!