[Python]4948번, 베르트랑 공준, 에라토스테네스의 체

문제

 

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. 

(11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17, 19, 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 

 

입력

 

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 케이스는 n을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0이 주어진다.

 

출력

 

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

 

풀이

 

이 문제는, 적어도 파이썬에선 Trial Division 테크닉을 사용해선 통과하지 못한다.

 

그저 시간초과 화면만 계속 구경해야 할 뿐..

 

자바로는 됐는데.. 투덜거리면서 한 번도 구현해 본 적 없던 에라토스테네스의 체 구현을 시작했다.

 

Sieve of Eratosthenes

 

에라토스테네스의 체는 고대 그리스의 수학자 에라토스테네스가 발명한, 소수 탐색 방법이다.

 

주어진 숫자가 소수인지 아닌지를 판별하는 것이 아닌, 주어진 범위 내에서 소수를 모두 찾는 방법 중에선

 

단순하지만 현존하는 가장 빠른 방법이라고 할 수 있다.

 

그 진행순서는 아래와 같다.

 

• 소수도 합성수도 아닌 1은 제외하고 시작한다.
• 다음으로 나오는 소수인 2의 제곱부터 시작해 2씩 더하며 지운다.
• 다음으로 나오는 소수인 3도 그 제곱부터 3씩 더하며 지운다.
• 5, 7, 11 ... 로 이어지며 같은 작업을 반복한다.

위의 작업에서 해당 소수의 배수를 전부 지우는 것이 아닌 제곱부터 지우는 이유는 간단한데,

 

제곱 이전의 배수(5를 예로 들면 10 = 5 x 2, 15 = 5 x 3, 20 = 5 x 4)는 이전 숫자의 판별에서

 

이미 지워졌기 때문이다.

 

이를 바탕으로 에라토스테네스의 체를 구현하면 아래와 같은 모양이 된다.

import math


def eratos(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(math.sqrt(n)) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False

    return [x for x in range(n + 1) if is_prime[x]]

마지막 줄은 처음 주어진 범위에서 소수인 것만 골라 리스트에 담은 뒤 리턴하는 코드이다.

 

이런 식의 리스트 생성 방식을 리스트 컴프리헨션이라고 하는 것 같던데, 빨리 익숙해여야지.

 

끝으로 전체 해답.

import sys
import math


def eratos(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(math.sqrt(n)) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False

    return [x for x in range(n + 1) if is_prime[x]]


while True:
    a = int(sys.stdin.readline().rstrip())
    if a == 0:
        break
    b = 2 * a
    print(len(eratos(b)) - len(eratos(a)))

eratos(n)로 만들어진 리스트의 인덱스 번호만 이용하면 조금 더 빨리 풀 수 있을 것 같은데,

 

일단 끝.