[백준 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

 

---

 

풀이

이 문제에선 제한시간이 1초라고 주어져서 기존에 했던 소수 갯수 구하기로 한다고 하면 시간초과가 뜹니다.
기존에 소수 갯수를 구할 때 했던 방식 : 소수찾기

시간초과를 해결하는 방법은 문제에 주어진 제한(1 ≤ n ≤ 123,456) 사이의 소수를 미리 구하는 방법인데요.
(단, n보다 크고 2n보다 작거나 같은 조건까지 생각해서 2*1 ≤ n ≤ 2*123,456)

그래서 저는 함수를 사용해서 함수 안에 숫자가 주어졌을 때 소수를 구하는 과정을 미리 넣고,
2*1 ≤ n ≤ 2*123,456 사이에 소수는 리스트 안에 미리 넣고,
주어진 수 n보다 크고 2n보다 작거나 같은 수가 있다면 갯수를 세어 출력했습니다.

그리고 기존에 제곱근을 사용했던 방식 (**0.5) 을 math.sqrt 를 사용해서 대체 했습니다.

코드를 순서대로 작성한다면
1. 소수를 구하는 함수
    1-1. 1은 소수에서 제외 False
    1-2. 2부터 제곱근 사이의 값 중 나눠지는 수가 있다면 False
    1-3. 1-1,1-2 가 해당하지 않는다면 소수 True
2. 소수를 담을 리스트 선언하고, 2*1 ≤ n ≤ 2*123,456 까지 함수에 대입하고 True면 리스트에 추가
3. 여러개의 입력, 0이면 출력 x
4. 소수 갯수를 카운트할 변수 선언
5. 소수를 담을 리스트안에 주어진 수보다 크고 주어진 수에 2를 곱한 수보다 작거나 같은 수가 있다면 카운트+1

※ sys.stdin.readline 을 쓰는 이유는 입력 시간 초과 때문입니다.
   한 두개의 입력일 때에는 input을 사용하고, 문제처럼 입력이 많을 때 sys.stdin.readline을 사용합니다.

---

작성 코드

import sys, math

def d(N): # 소수를 찾는 함수
    if N == 1:
        return False
    for i in range(2, int(math.sqrt(N))+1):
        if N % i == 0:
            return False
    return True
    
sosu = [] # 소수를 담을 리스트 선언
for i in range(2, 2*123456) # 조건 범위안에 소수를 찾고 리스트에 추가
    if d(i):
        sosu.append(i)
        
while True:
    N = int(sys.stdin.readline()) # 입력이 여러개 일땐 sys 사용
    cnt = 0 # 갯수세기
    
    if N == 0: # 0이 입력되면 출력X
        break
        
    for i in sosu: # 소수 리스트안에 숫자를 하나씩 꺼내서 확인
        if N < i <= 2*N: # N보다 크고 2N보다 작거나 같으면 갯수 카운트 +1
            cnt += 1

    print(cnt)