🐷전동준(Jeon DongJun)

Go with the flow

[BOJ/백준-Python]4948번 - 베르트랑 공준

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보다 작거나 같은 소수의 개수를 출력한다.

제한

  • 1 ≤ n ≤ 123,456

예제 입력 1

1
10
13
100
1000
10000
100000
0

예제 출력 1

1
4
3
21
135
1033
8392

해결할 방법을 생각해보자.💡

1929번처럼 에라토스체네스의 체를 사용해서 풀 수 있는 문제다.

예제를 보면 0이 입력되었을 때, input이 끝난다.

빈 리스트를 만들어 놓고 while문을 사용해 순서대로 숫자들을 입력받아서 append해준다. 0(False)이 입력된다면 중단되게 만들자.

inpurt_lst = []
while True:
    n = int(input())
    if n:
        input_lst.append(n)
    else:
        break

문제의 제한을 보면 n의 최대값은 123,456이다. 우리는 2n이하의 값들 중에서 소수를 찾아야 하므로 최대값은 123456 * 2 이다.

max = 123456 * 2

1912번과 마찬가지로 에라토스체네스의 체를 사용할 것이다.

리스트 안에 최대값 + 1만큼의 불리언원소를 만들어준다.(True로) 인덱스를 사용할 것이기 때문이다.

0과 1은 소수가 아니므로 False로 바꿔놓는다.

eratos = [True] * (max+1)
eratos[0] = False
eratos[1] = False

에라토스체네스의 체에서 소수를 구할 범위의 최대값의 루트를 씌운 값이 반복문을 반복할 범위다.

for i in range(2, int(max ** 0.5) + 1):

만약, 해당 값이 False가아니라 True로 살아있다면 소수 2부터 배수를 모두 지워주는 식으로 코드를 짜준다.

	if eratos[i]:
        j = 2
        while i * j <= max:
            eratos[i * j] = False
            j += 1

이러면 체를 사용해서 소수인 인덱스만 True 상태로 남아있을 것이다.

이제 마지막으로 전에 받아놓은 입력값들 각각을 구해놓은 리스트의 인덱스와 비교해 소수들의 개수를 출력해주면 된다. 범위는 초과~이하로 잘 설정해주자.

for i in input_lst:
    result =  0
    
    for j in range(i+1, 2*i+1):
        if eratos[i]:
            result += 1
    print(result)

코드💻

input_lst = []
while True:
    n = int(input())
    if n:
        input_lst.append(n)
    else:
        break

max = 123456 * 2
eratos = [True] * (max+1)
eratos[0] = False
eratos[1] = False
for i in range(2, int(max ** 0.5)+1):
    if eratos[i]:
        j = 2
        while i * j <= max:
            eratos[i * j] = False
            j += 1


for i in input_lst:
    result = 0

    for j in range(i+1, 2*i+1):
        if eratos[j]:
            result +=1 
    print(result)

해결 로그

문제 푼 날짜 체크
2022-06-13 ✔
   
   
   
   

2022

[web]jQuery 복습 3

1 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]jQuery 복습 2

13 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]jQuery 복습 1

14 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리4

5 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리3

10 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리2

7 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리1

8 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]CSS 기초 정리

11 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]HTML 기초 정리

8 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[Pandas]pandas 연습

3 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

맨 위로 이동 ↑

2021

[Python기초]module

1 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

맨 위로 이동 ↑