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

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

4948번: 베르트랑 공준

 

 

---

코드 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는 메모리를 적게 사용했다.

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