백준 4948번 (F)

백준 온라인 저지 4948번 베르트랑 공준

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.
이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.
예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)
자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.

---

제한 사항

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.
입력의 마지막에는 0이 주어진다.

---

처음 내 생각

• 실버2 문제다. 긴장을 좀 했다.
• 하지만 문제의 원리 자체는 어렵지 않다고 느꼈다. 이 전 문제에서 범위가 달라졌을 뿐이니까.
• 그렇게 내가 가지고 있던 소수 판별 함수를 사용해 또 작성을 해 봤더랬다.

from math import sqrt

def isPrime(n):
    if n < 2:
        return False
    elif n == 2:
        return True
    
    for i in range(2, int(sqrt(n))+1):
        if n % i == 0:
            return False
    
    return True

while True:
    n = int(input())
    if n == 0:
        break

    result = 0
    for number in range(n+1, 2*n+1):
        if isPrime(number):
            result += 1
    
    print(result)

• 아.. 그저.. 시간초과.
• 틀리는 것만 넣고 돌리나 싶기도 한데, 이게 테스트 케이스만으로는 직관적으로 알기 힘들기도 하지 않은가?
• 테스트 케이스는 항상 맞았고, 논리는 정확하다는 이야기긴 하다. 백준이 실전에선 의외로 도움이 안 된다는 말의 의미를 깨닫는 중
• 시간복잡도의 계산을 생활화해야겠다는 생각도 얼핏 하게 됐다.

---

또 시간초과야?

• 이번엔 또 뭐가 문제야?! 성질나서 같은 케이스, 이름만 바뀐 케이스로 몇 번 제출했던 것 같다.
• 시간을 줄이기 위해 에라토스테네스의 체도 활용해 봤다. 하지만 결국 별 차이 안나더구만?

isPrime = [True] * 250000
isPrime[0] = False
isPrime[1] = False

for i in range(2, len(isPrime)):
    if isPrime[i] == True:
        for j in range(i+1, len(isPrime)):
            if j % i == 0:
                isPrime[j] = False

while True:
    n = int(input())
    if n == 0:
        break

    result = [x for x in range(n+1, 2*n+1) if isPrime[x]]
    print(len(result))

• 결국 또 구글의 도움을 구할 수 밖에 없었는데..

---

뭐야 맞잖아?

• 글에서 찾아본 풀이는, 놀랍게도 소수 판별하는 법이 평소 나랑 같았다.
• 아니 그럼 대체 뭐가 문젠데? 라고 생각하고 보니, 이분은 소수들을 주어진 범위 내에서 미리 따로 빼 놨다..
• 나는 이걸 매번 계산하고 앉았으니, 시간 초과가 날 수 밖에 없었던 것.

from math import sqrt

def isPrime(n):
    if n < 2:
        return False
    elif n == 2:
        return True

    for i in range(2, int(sqrt(n)) + 1):
        if n % i == 0:
            return False
    
    return True

nums = list(range(2, 250000))
primes = [x for x in nums if isPrime(x)]

while True:
    n = int(input())
    if n == 0:
        break
    
    result = 0
    for number in primes:
        if n < number <= 2*n:
            result += 1
    
    print(result)

• 이걸 빠른 시간 안에 작동하게 짠다고 얼마나 이득일진.. 내가 기계와 가까운 프로그래머가 되지 않는 한 모를 것 같다.