[백준/Python] 4948번 베르트랑 공준 (기본수학2)

4948번 : 베르트랑 공준 문제

 

 

베르트랑 공준은 임의의 자연수 n에 대하여,

n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

 

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

 

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

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

 

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

 

 

 

https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

 

---

 

풀이 코드

 

import math

m = 123456

sosu = [True for _ in range(2 * m + 1)] 
sosu[0], sosu[1] = False, False


for i in range(2, int(math.sqrt(2 * m) + 1)):

    if sosu[i]: 
        j = 2 

        while i * j <= 2 * m: 
            sosu[i * j] = False 
            j += 1 


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

    count = 0

    for i in range(n+1, 2 * n + 1): 

        if sosu[i]: 
            count += 1 

    print(count)

 

 

import math

 

 

- 아래의 코드에서 제곱근을 구하는 sqrt() 함수를 사용하기 위해 import

 

 

 

m = 123456

 

 

- 문제에서 입력값의 범위는 1 ~ 123,456

 

- 입력값 범위의 최댓값인 123,456으로 변수 m 을 초기화

 

 

 

sosu = [True for _ in range (2 * m + 1)]

 

 

- 0부터 2m 까지의 정수가 순차적으로 저장되어 있는 리스트 sosu 선언

 

- sosu 리스트를 통해 소수를 판별할 수 있음

 

- 원소의 값이 소수인 경우 True, 아닐 경우 False

 

 

 

sosu[0], sosu[1] = False, False

 

 

- 0은 소수에 해당하지 않으므로, sosu[0] 값을 Fasle 로 재설정

 

- 1은 소수에 해당하지 않으므로, sosu[0] 값을 Fasle 로 재설정

 

 

 

for i in range(2, int(math.sqrt(2 * m) +1)):

 

 

- i 값이 약수인지 확인하기 위해서는, 2부터 제곱근 값까지 순회해야 함

 

- 1보다 큰 자연수로 나누어야 하므로, 2부터 시작

 

- math.sqrt(수) 를 통해 특정 수의 제곱근을 구할 수 있음

 

- range() 를 사용하여 2부터 제곱근 2*123456 까지 for 문을 반복

 

 

 

 

if sosu[i]:    /    j = 2

 

 

- sosu 리스트의 i 인덱스 값이 True 인 경우

 

- 즉, i 값이 소수인 경우

 

- i 에 곱해줄 값을 나타내는 변수 j 선언, 2로 초기화

 

 

 

while i * j <= 2 * m:

 

 

- i 곱하기 j 의 값이 2 * 123456 보다 작거나 같은 경우 while 문 반복

 

- i 곱하기 j 의 값이 2 * 123456 보다 커질 경우, 문제에서 제시된 값의 범위를 넘어가게됨

 

 

 

sosu[i * j] = False

 

 

- i * j 값은 소수가 아님

 

- sosu[i * j] 값을 False 로 설정

 

 

 

j += 1

 

 

- j 값을 1씩 증가하며, while 문 반복

 

 

 

while True:    /    n = int(input())

 

 

- 각각의 테스트 케이스 입력값이 한 줄 씩 주어지므로, while 문 안에 input() 작성

 

- 입력값을 변수 n 에 저장

 

 

 

if n == 0:    /    break

 

 

- n 이 0 인 경우

 

- while 문을 빠져나오기 위한 break 작성 

 

 

count = 0

 

 

- n 보다 크고, 2n 보다 작거나 같은 소수의 개수를 세기 위한 변수 count 선언

 

- 0으로 초기화

 

 

 

for i in range(n+1, 2 * n + 1):

 

 

- range() 를 사용하여, n+1 부터 2n 까지 for 문 반복

 

- n 보다 커야 하므로, n+1 부터 시작

 

 

 

if sosu[i]:    /    count += 1

 

 

- sosu 리스트의 i 인덱스 값이 True 인 경우

 

- 즉, i 값이 소수인 경우

 

- 소수의 개수를 나타내는 변수 count 값 1 증가

 

 

 

print(count)

 

 

- 소수의 개수인 count 값 출력

 

 

 

 

 

 

 

나동빈 '이것이 코딩 테스트다 with 파이썬' 책을 참고하여 작성하였습니다.

https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC,