[BAEKJOON] 백준 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 ≤ n ≤ 123,456

---

코드 (1차 -실패)

def isPrime(x):
    if x == 1:
        return False
    else:
        for i in range(2, int(x**0.5)+1):
            if x % i == 0:
                return False
        return True

while True:
    n = int(input())
    
    if n == 0:
        break
    
    prime = 0
    for i in range(n+1, 2*n+1):
        if isPrime(i):
            prime += 1
    print(prime)

문제 요약

자연수 n이 주어졌을 때, n보다 크고, 2n 이하의 소수의 개수를 구하는 프로그램을 만드는 문제이다.

직전에 푼 1929번 소수 구하기 문제의 에라토스테네스의 체를 이용하면 될 것이다.

코드 설명

1. 에라토스테네스이 체 방법을 이용하여 숫자의 제곱근 까지만 약수의 여부를 검증하는 함수 isPrime을 생성한다.
2. 1은 소수가 될 수 없기 때문에 False를, 1 초과 숫자들 중 2이상의 특정 숫자의 제곱근 까지 for문을 통해 소수를 검증한다.
3. 만일 특정 숫자가 제곱근 미만의 숫자로 나누었을 때 0 또는, 제곱근이 정수로 존재하는 경우 나머지가 0이 된다면, 소수가 아니므로 False를 반환하고, 나누어지지 않을 경우 True를 반환한다.

   def isPrime(x):
       if x == 1:
           return False
       else:
           for i in range(2, int(x**0.5)+1):
               if x % i == 0:
                   return False
           return True​

    
4. 한 줄마다 n이 입력이 되므로(복수 개의 n이 한 줄씩 입력됨), while문을 True로 생성한 뒤, 주어진 조건에 따라 n이 0이 올 경우 while문을 탈출한다.

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

5. 소수의 개수를 구하기 위해 prime 변수를 선언하고 0을 할당한다.
6. for문을 통해 n 초과, 2n 이하의 수를 순회하며, isPrime 함수에서 True로 반환된 개수를 prime 변수에 추가한 뒤, for문이 끝나면 prime을 출력한다.

결과

또 시간초과가 떴다. 에라토스테네스의 체 방법을 이용하되, 시간을 줄일 방법을 찾아야했다.

공준이가 진짜 또 귀찮게하네 ㅂㄷㅂㄷ

---

코드

num = 123456*2+1
num_list = [1]*num
for i in range(1, num):
    if i == 1:
        continue
    for j in range(2, int(i**0.5)+1):
        if i % j == 0:
            num_list[i] = 0
            break

while True:
    n = int(input())
    
    if n == 0:
        break
    
    prime = 0
    for i in range(n+1, 2*n+1):
            prime += num_list[i]
    print(prime)

코드 설명

1. 에라토스테네스의 체를 이용하되, 함수 생성이 아닌 시간을 단축시킬 방법이 필요하다.
2. 이는 코드가 실행됨가 동시에 미리 입력될 수들까지의 소수를 미리 구한 뒤, 소수의 개수를 더해주어 소수의 개수를 구하는 것이다.
3. 해당 문제는 123456까지라는 제한된 수가 존재하므로, 123456*2 + 1개의 인자가 1 인 리스트를 생성한다.
   (이때 첫 번째 리스트는 사용되지 않기 때문에 + 1을 하는 것이다.)

   num = 123456*2+1
   num_list = [1]*num​

4. 첫 번째 for문에서 1부터 123456*2 까지 순회하며 소수를 찾는다.
5. 1은 소수가 될 수 없으므로 넘어가고, 2부터 에라토스테네스의 체를 이용하여 두 번째 for문을 순회한다.
6. 2부터 첫 번째 for문에서 전달받은 i의 제곱근 까지 순회하며, i가 자신의 수 이하의 숫자에 의해 나누었졌을 때 나머지가 0인 경우, 해당 인덱스의 값을 0으로 변경하고, for문을 탈출한다. 
   이 때 해당 숫자가 소수인 경우, 해당 인덱스의 리스트 값은 여전히 1이다.
7. while문을 통해 각 n을 입력받고, n이 0이 될 경우, while문을 멈춘다.

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

8. 소수의 개수를 구하기 위해 prime 변수를 선언하고, n 초과 2n 이하의 소수 개수를 for문을 통해 구한 뒤, for문이 끝날 경우 prime 변수를 출력하여 값을 구한다.