[백준] 4948번 베르트랑 공준 | 파이썬 Python

문제

베르트랑 공준은 임의의 자연수 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보다 작거나 같은 소수의 개수를 출력한다.

 

예제

 

나의 풀이1

import math

cases = []

while True:
    num = int(input())

    if num == 0:
        break
    else:
        cases.append(num)

for num in cases:
    min = num + 1
    max = num * 2
    
    nums = {i : True for i in range(min, max + 1)}
    cnt = min - 1

    for i in range(2, int(max**0.5) + 1):
        total = i * math.ceil(min/i)

        while total <= max:
            if nums[total]:
                nums[total] = False
                cnt -= 1
            total += i

    print(cnt)

• 처음엔 입력값마다 딕셔너리를 따로 만들어서 에러토스테네스의 체 를 이용해 소수의 개수를 측정했다.
• 하지만 이 방법은 시간 초과로 실패했다.

 

나의 풀이2

max = 123456*2
nums = {i : True for i in range(2, max+1)}

for i in range(2, int(max**0.5)+1):
    cnt = 2
    while i*cnt <= max:
        if nums[i*cnt]:
            nums[i*cnt] = False
        cnt += 1

while True:
    num = int(input())

    if num == 0:
        break
    else:
        cnt = 0
        for i in range(num+1, (num*2)+1):
            if nums[i]:
                cnt += 1
    print(cnt)

• 최대 입력값인 `123,456`의 두 배를 길이로 가지는 딕셔너리를 생성했다.
• 이 딕셔너리 하나에 대해서만 에러토스테네스의 체를 이용해 해당 숫자가 소수인지를 판별한다.
  • `2`에서 최댓값의 제곱근까지 for문을 실행하면서 `n`의 배수를 계속 지워나간다.
  • `cnt = 2`부터 시작하는 이유: 예를 들어 `11`의 배수를 탐색하는 경우 `11` 자신은 소수에서 제외할 수 없다.
• 최종적으로 for문을 실행해서 입력값마다 해당 범위의 소수 개수를 측정해서 출력한다.

 

나의 풀이3

import math

cases = []

while True:
    num = int(input())

    if num == 0:
        break
    else:
        cases.append(num)

sorted_cases = sorted(cases)

min = sorted_cases[0] + 1
max = sorted_cases[len(cases) - 1] * 2

nums = {i : True for i in range(min, max + 1)}

for i in range(2, int(max**0.5) + 1):
    total = i * math.ceil(min/i) * 2

    while total <= max:
        if nums[total]:
            nums[total] = False
        total += i

for num in cases:
    cnt = 0

    for i in range(num + 1, num*2 + 1):
        if nums[i]:
            cnt += 1
            
    print(cnt)

• `123,456`을 최댓값으로 잡으면 불필요한 연산이 실행될 수 있기 때문에 실제로 입력받은 값의 최소 최댓값만큼을 범위로 하는 딕셔너리를 생성했다.
• 딕셔너리의 범위를 제외하면 풀이2와 똑같은 풀이다.
• 하지만 실행속도 면에서는 두 풀이가 별 차이가 없었다.