[Python/코테] 백준 4948 베르트랑 공준

4948 베르트랑 공준

문제 및 조건 설명: https://www.acmicpc.net/problem/4948

알고리즘 설계

• 합성수 N에서 1을 제외한 가장 작은 약수는 $\sqrt N$ 이라는 효율적인 소수 판정법을 사용한다. 
• 특정 구간의 소수를 구하는 것이므로 에라토스테네스의 체 알고리즘을 사용할 수 있다.
• 중요한 것은 시간초과 !

알고리즘 구현

참고: https://ji-gwang.tistory.com/218

* pypy3으로 제출하지 않으면 시간초과 판정.

import sys

m = 123456
array = [True for i in range(2*m+1)]
array[0], array[1] = False, False
# 미리 합성수 제거
end = (int)((2*m) ** (1/2))

for i in range(2, end + 1):
    if array[i] == True:
        j = 2
        while i * j <= (2 * m):
            array[i*j] = False
            j += 1


n = int(sys.stdin.readline().strip())
while n != 0:
    cnt = 0

    # 구간의 소수 갯수 세기
    for i in range(n+1, 2*n+1):
        if array[i] == True:
            cnt += 1

    print(cnt)
    n = int(sys.stdin.readline().strip())

 

나다어

• 여러 입력이 주어진다면, 매번 소수를 검사하는 것은 불필요하다.
• 에라토스테네스의 체는 제곱근까지만 검사해도 결과가 같다는 것을 유의하자.

* 오답 코드

import sys


n = int(sys.stdin.readline().strip())
while n != 0:
    array = [True for i in range(2*n+1)]
    array[0], array[1] = False, False
    cnt = 0

    # 합성수 제거
    end = (int)((2*n) ** (1/2))
    for i in range(2, end + 1):
        if array[i] == True:
            j = 2
            while i * j <= (2 * n):
                array[i*j] = False
                j += 1

    # 구간의 소수 갯수 세기
    for i in range(n+1, 2*n+1):
        if array[i] == True:
            cnt += 1

    print(cnt)
    n = int(sys.stdin.readline().strip())

• 에라토스테네스의 체로 구현하려다, n부터 시작한다는 조건에서 구현이 막혀버렸다.
      → n부터만 계산할 수는 없다. 2부터 시작해야 한다. 
• while 문 내부에서 에라토스테네스의 체를 구현했다가 시간 초과 판정을 받았다.
      → 문제에서 주어진 최대 입력값의 길이로 배열을 만든 뒤, 미리 모든 구간에 대한 소수 판별을 실시해두고 입력때마다 개수만 세어준다.