[백준] 기본 수학 2 - 4948번 (Python)

https://www.acmicpc.net/problem/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)

def sosu(num):
    if num==1: # 1은 모든 수의 약수
        return False
    else:
        for i in range(2, int(num**0.5)+1): # 제곱근의 수 중에서
            if num%i == 0: # 약수가 있을 경우
                return False
        return True

while True:
    cnt = 0 # 카운트 세야함
    n = int(input()) # 입력받기
    if n == 0: # 입력받은 값이 0이면 종료
        break
    for i in range(n, 2*n+1):
        if sosu(i):
            cnt += 1
    print(cnt)

(2)

def sosu(num):
    if num==1: # 1은 모든 수의 약수
        return False
    else:
        for i in range(2, int(num**0.5)+1): # 제곱근의 수 중에서
            if num%i == 0: # 약수가 있을 경우
                return False
        return True

all_list = list(range(2,246912)) #문제에서 제한한 2부터 2*123,456 범위
memo = [] #for문 밖에 리스트 정의

for i in all_list:
    if sosu(i):	#sosu함수에 해당하면
        memo.append(i) #리스트에 추가

n = int(input()) # 입력받기

while True:
    cnt = 0 # 카운트 세야함
    if n == 0: # 입력받은 값이 0이면 종료
        break
    for i in memo:
        if n < i <=2*n:
            cnt += 1
    print(cnt)
    n = int(input()) # 다시 입력받기

풀이

저번 1929번의 문제와 비슷한 유형의 문제이다. 그렇기에 저번에 했던 방식과 비슷하게 하게 된다면 나오지 않을까 하여 (1)번과 같은 형식으로 코드를 짜본 후 코드를 돌려보았다. 혼자 해보았을 때는 결과가 잘 나왔지만 백준에 넣고 돌려보자 시간초과라는 문구가 나왔다. 그래서 눈물을 머금고 다시 한 번 구글의 힘을 빌려보았다. 그 결과가 (2)번 코드이다.

 

큰 틀은 별 다를게 없다. 1929번과 마찬가지로 반복문과 def문을 이용하여 함수를 만들고 결과를 반환받는 형식으로 이루어져있다. 다른 점이 있다면 모든 소수가 아닌 문제 내 제한한 범위 1 <= n <=123,456 안에서의 소수만 저장하고 for 문이 실행되는 동안 리스트에 있는 소수들을 꺼내오는 방식으로 풀었다는 점이다.

 

• 1행 : def sosu(num) 즉, sosu(i)의 값을 가져와 num으로 변형 후 2~8행을 실행한다.
• 2~3행 : num에 저장된 값이 1이라면 False를 리턴한다.
• 4행 : if가 참이 아닐 시 5~8행을 실행한다.
• 5행 : 2부터 num에 저장된 값을 제곱근 시킨 값까지를 i에 선언한다.  제곱근까지의 약수를 구하면 해당 약수를 포함하는 수를 모두 제거할 수 있다고 한다. ex) i = 12에서 12의 약수는 1 2 3 4 6 12가 된다. int(sqrt(12)) = 3이고 12는 3으로 나누어 떨어지므로 더 검사할 필요가 없다고 한다. (나는 잘 모르겠다...)
• 6~7행 : num을 i로 나눈 값의 나머지가 0일 경우 false를 리턴하여 값을 돌려주지 않는다.
• 8행 : 6~7의 값에 충족하지 않아 리턴이 되지 않을 경우 작동된다. True를 반환하여 num에 저장된 값을 반환한다.
• 10행 : 문제의 범위 안에 존재하는 값들을 리스트 형식으로 all_list 란 변수에 저장한다.
• 11행 : 리스트 형식의 memo란 이름의 변수를 생성한다.
• 13~15행 : all_list에 존재하는 전부 for문과 if문을 사용하여 memo 리스트에 주가한다.
• 17행 : 숫자 하나를 입력받아 변수 n에 저장한다.
• 19~26행 : break 문이 걸리기 전까지 반복이 된다. 발생된 횟수가 존재해야 하기 때문에 cnt란 변수를 만들어주며 0일때 종료되어야 하는 조건을 해결하기 위하여 if문을 이용하였다. for문을 이용하여 memo 의 값을 i 에 넣어주며 if문을 충족할 시 cnt 의 값을 1씩 증가시키고 cnt에 저장된 값을 출력한다. 이후 다시 입력을 받기 위해 같은 변수와 input()을 사용해준다.