백준 4948 : 베르트랑 공준 (파이썬)

https://www.acmicpc.net/problem/4948 문제 풀이

4948번: 베르트랑 공준

---

베르트랑 공준

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

55293

22140

17998

40.406%

문제

베르트랑 공준은 임의의 자연수 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

import sys
nums=[]
#입력
for line in sys.stdin:
    if int(line.rstrip()) == 0 : break
    nums.append(int(line.rstrip()))
#에라토스테네스 체
isPrime = [True if i>1 else False for i in range(max(nums)*2+1) ]
for i in range(len(isPrime)) :
    if isPrime[i] :
        for multiple in range(i*2,len(isPrime),i) :
            isPrime[multiple] = False
#출력
for num in nums :
    print(isPrime[num+1:num*2+1].count(True))

결과

해설

매 입력마다 에라토스테네스의 체를 돌리는 것보다(이중 포문 써야 함) 입력값을 전부 다 받고 난 뒤 최대 값을 기준으로 에라토스테네스의 체 알고리즘을 통해 소수 목록을 구해놓는 것이 더 빠를 거라 생각했다. 

(에라토스테네스의 체에 대한 내용은 https://teching.tistory.com/5에서 확인할 수 있다!)

에라토스테네스의 체(소수 판별 알고리즘)

그 후 출력부를 따로 만들어 isPrime배열의 n+1부터 2n까지의 범위의 합을 구해주면 끝! (True = 1, False = 0)

---

코드 2

import sys
for line in sys.stdin :
    n = int(line)
    isPrime = [1]*n
    if not isPrime : break
    for i in range(2,int((2*n)**.5)+1):
        # for mul in range(-(n+1)%i,len(isPrime),i) :
        #     isPrime[mul] = 0
        isPrime[-(n+1)%i::i] = [0]*(2*n//i-n//i)
    print(sum(isPrime))

결과

해설

두 번째 코드는 정답을 맞힌 후에 다른 사람들은 어떻게 풀었나 구경중 놀라운 코드를 보아서 그걸 보고 응용해서 만들어봤다.

바로 에라토스테네스의 체를 n~2n범위만 새롭게 구해주는 것이다!!

isPrime[-(n+1)%i::i] = [0]*(2*n//i-n//i)

이 알고리즘의 핵심은 이 부분이다. 내가 본 사람은 ~(n)% i로 썼는데 이를 보고 처음에는 이해하기가 어려웠다. 그래서 한번 예로 n=0~19 , i=3으로 잡고 쭉 나열을 해봤다.

이렇게 써놓고 열심히 규칙을 찾아보았고 나는 정확한 동작 원리를 알고 싶었다. 그래서 하나하나 동작을 뜯어보았다.

 

'~'연산자

'~'연산자는 비트 연산자로 1의 보수를 취해주는 연산자인데 컴퓨터가 사용하는 보수는 2의 보수이기 때문에 1의 보수를 취해주면 -(n+1)과 같은 연산을 한다.

 

'%'연산자(모듈러)

피제수= 몫*제수 + 나머지( a = q*n+r )로 나타낼 수 있을 때,
피제수% 제수 =나머지(a% n = r)가 되는 것이고 피제수//제수=몫(a//n = q)이 되는 것이다.
(예를 들어 -3%5 경우, -3= -1*5 + 2로 표현할 수 있다. 그러므로 -3%5 = 2, -3//5는 -1이 나온다.)

즉, 쉽게 말하면 i의 배수가 되기 위해서 n에게 필요한 값을 알려준다!

 

나는 보고 무슨 코드인지 알기 쉽게 ~를 사용하지 않았다.

---

나는 아래 코드의 시간이 짧을 거라고 생각했다. 하지만 놀랍게도 내가 처음 만든 코드가 더 짧게 걸렸다.

이는 아무래도 입력이 많아질수록 코드 2는 에라토스테네스의 체 알고리즘을 반복적으로 사용을 하기 때문인 것 같다.

대신 코드 2는 메모리를 적게 사용했다.

이번 문제를 통해 % 연산과 ~연산에 대해 좀 더 자세히 알 수 있어서 좋은 문제였다!