백준 python 문제 - 베르트랑 공준(4948)

베르트랑 공준(4938)

[문제 간단 설명]

자연수 N에 대하여 N보다 크고 2N보다 작거나 같은 수에 대하여 사이에 소수가 적어도 1개는 존재하는 것을 증명하는 프로그램을 제작한다.

 

[문제 풀이 핵심]

1. N을 입력 받고, N과 2N의 사이의 범위를 지정해야 한다.

2. 사이에 소수를 구하는 프로그램을 제작하고, 그 수를 측정하는 방식을 사용한다.

3. 테스트 케이스의 개수는 따로 정해지지 않았으며, 0이 입력되는 순간 프로그램이 종료되어야 한다.

 

[문제 풀이 과정]

1. 에라토스테네스의 체의 원리를 이용한다. 에라토스테네스의 체란 2부터 시작해서 각각 숫자의 배수를 지워나가는 과정을 의미힌다. 이 과정을 사용하면 하나하나 숫자를 확인하는 것보다 작동 시간을 획기적으로 줄일 수 있다.

 

[소스 코드]

import sys
#파이썬은 값이 0 이면 False로 처리를 한다.

#체를 이용하여 소수를 구하자.
def is_demicial(a):
    count = 0
    new_a = int((2*a)**0.5)
    demical_list = [False, False] + [True]*(2*a-1)
    for i in range(1, new_a+1):
        if demical_list[i] == True:
            for j in range(2*i, 2*a+1, i):
                demical_list[j] = False
    for i in range(a+1, 2*a+1):
        if demical_list[i] == True:
            count += 1
    print(count)
while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    else:
        is_demicial(n)

 

[작동 원리]

1. 소수 판별하는 함수를 제작한다. 에라토스테네스의 체를 이용한 것으로 전의 풀이에서도 등장했다. 차이점은 숫자를 출력하는 대신, True가 나올 때마다 conut가 올라가게 하여 총 숫자의 개수를 세는 것으로 만들었다.

2. while의 True로 무한 반복을 하게 만들고, 만약 n이 나오면 break로 반복문을 빠져나오게 만들었다.