비트마스크를 이용한 에라토스테네스의 체 배우기

1. 에라토스테네스의 체 기본형태

 

n이하의 소수를 구하는 알고리즘

 

n+1개의 1을 가지는 리스트로 초기화하고, 2부터 n의 제곱근까지 순회하여 해당 수의 배수를 모두 지우고 나면

 

소수만 남는다는 알고리즘이다

 

n = int(input())

result = [1]*(n+1)

for i in range(2,int((n+1)**(1/2))+1):
    
    if result[i] == 1:
        
        for j in range(i*i,n+1,i):
            
            result[j] = 0

prime_list = [i for i in range(2,n+1) if result[i] == 1]

 

여기서 j의 시작 지점을 i+i로 하는 경우가 많은데, i*i로 해도 된다.

 

왜냐하면, i+i는 결국 가장 먼저 2의 배수에서 지워지기 때문이다.

 

2. 에라토스테네스의 체 문제점

 

에라토스테네스의 체는 구현 형태를 보면 1부터 n까지 모든 값에 대한 소수 여부를 result라는 리스트에 0 아니면 1로 저장해둔다는 특징이 있다.

 

그러므로 공간 메모리를 상당히 많이 잡아먹는다.

 

기본적으로 pypy3 기준으로 n이 $10^{8}$이면 256mb를 넘어가서 메모리 초과가 난다..

 

 

3. 비트마스크를 이용한 에라토스테네스의 체

 

기본형태는 result라는 리스트에서 하나의 공간에 대해 하나의 소수 여부만 담는다는 특징이 있다.

 

공간 메모리를 개선하고 싶다면, 하나의 공간에 여러 수의 소수 여부를 담는다면 어떨까?

 

기본형태는 한 원소가 0 아니면 1로 이진수에서 1비트만 가지고 있는데,

 

이번에는 한 원소에 8개의 비트를 담는 것이다. 8자리의 이진수를 하나의 원소에 담는 것이다.

 

 

 

위 그림은 어떤 8비트 2진수를 나타낸 것이다.

 

각 비트는 0부터 7까지의 인덱스를 가지며, 한 원소에 위와 같은 8비트의 수를 담는다면

 

각 비트의 0, 1 상태를 통해 0부터 7까지 8개의 정수의 소수 여부를 하나의 공간만으로 알 수 있다.

 

따라서, 배열의 한 원소에 0,1 비트를 한 개만 쓰는 대신에 8개의 비트를 사용한다면 필요한 배열의 크기는 원래 n이었다면

 

n//8로 줄어든다.

 

 

4. 알고리즘

 

4-1) 8비트 2진수는 어떻게 나타내는가?

 

한 원소에 8비트 2진수를 담아야하는데 어떻게 담는가?

 

10진수로 255는 8자리 2진수를 나타낸다.

 

 

 

255를 원소로 갖는 n//8 크기의 result로 초기화하는 것으로 시작한다.

 

 

4-2) 내가 판별하려는 숫자 i는 result에서 어디에 위치하는가?

 

간단하게 생각해보면..

 

0,1,2,3,4,5,6,7은 0번에

 

8,9,10,11,12,13,14,15은 1번에

 

16,17,18,19,20,21,22,23은 2번에

 

24,25,26,27,28,29,30,31은 3번에

 

...

 

특징을 보면 각 그룹은 8로 나눈 몫에 위치한다

 

https://deepdata.tistory.com/492

비트마스킹을 위한 비트연산 필수이론 가볍게 정리

 

비트를 사용하니까 비트연산을 사용하는게 맞겠지

 

오른쪽으로 옮기는 >> 연산 3번 하면 $2^{3}$으로 나누는 것과 마찬가지이다.

 

따라서 result[i >> 3]에 내가 판별하고자 하는 숫자 i가 존재한다

 

 

4-3) 내가 원하는 숫자 i가 비트 내에서 어디에 위치하는가?

 

result의 어디 인덱스에 존재하는지 알아냈지만, 그렇다면 해당 인덱스 내의 어디 비트에 존재하는지를 알아야한다.

 

https://deepdata.tistory.com/823

정수 n을 2의 거듭제곱으로 나눈 나머지를 효율적으로 구하는 방법

 

해당 i와 7과 &연산을 수행하면 0,1,2,3,4,5,6,7중 하나이다. 

 

이는 8비트 2진수 "11111111"에서 i가 어디에 위치할지를 나타내는 인덱스로 볼 수 있다.

 

그 다음에 1과 <<으로 k만큼 비트연산을 수행하면 0으로 된 8비트 2진수에서 오른쪽에서 k번 위치를 1로 켜준다.

 

예를 들어 1 << 5는 "00100000"가 된다.

 

둘을 종합하면, 1 << (i & 7)을 수행하면... 0으로 된 8비트 2진수에서 i의 위치만 1로 켜진다.

 

 

4-4) 소수가 아닐때 체에 표시하는 방법

 

기본 원리는 어떤 수 i가 소수라면.. 해당 비트를 1로 켜주고 소수가 아니라면 해당 비트를 0으로 하면 된다.

 

i가 result내 어디 인덱스에 존재하는지는 result[i >> 3]으로 나타낼 수 있다.

 

i가 8비트 2진수 내에서 어디 비트에 존재하는지는 1 << (i & 7)로 나타낼 수 있다.

 

비트연산 & 연산을 수행하면 1과 & 연산을 수행하면 해당 비트는 그대로 가지고 오고 0과 & 연산을 수행하면 해당 비트는 0으로 만든다

 

비트연산 ~ 연산은 해당 비트열을 모두 뒤집는다. 1은 0으로 0은 1로

 

 

만약 i가 소수가 아니라면 어떻게 해야할까? 

 

i의 비트 위치를 0으로 만들면 된다.

 

result[i >> 3]은 i의 result 내 위치를 나타내고... 1 << (i & 7)은 i의 8비트 내 위치를 나타낸다.

 

그런데 i가 소수가 아니므로.. result[i >> 3]으로 가져온 2진수 8비트 열에서 i의 비트 위치를 0으로 만들어야한다.

 

여기서 1 << (i & 7)은 i의 8비트내 위치를 가리키고, 나머지는 모두 0으로 된 비트열인데

 

~연산을 이용해서 ~(1 << (i & 7))을 한다면.. i의 위치만 0으로 하고 나머지는 모두 1로 만든 8비트열이 된다

 

그리고 result[i >> 3] = result[i >> 3] & ~(1 << (i & 7))을 수행한다면?

 

i의 위치를 result[i >> 3]에서 0으로 바꿔버리고,

 

i의 위치가 아닌 나머지는 모두 1과 & 연산을 수행하므로 원래 result[i >> 3]의 비트 값을 그대로 가지고 온다.

 

따라서 i가 소수가 아니라면.. result[i >> 3] &= ~(1 << (i & 7))로 해당 i의 비트 위치를 0으로 만들어준다.

 

--------------------------------------------------------------------------------------------------------

 

숫자로 생각해보면 간단하다

 

result[i >> 3] = "01011000"이고..

 

1 << (i & 7) = "00010000"이다.

 

그런데 i가 소수가 아니다?

 

~(1 << (i & 7)) = "11101111"이다.

 

result[i >> 3] = "01011000"에서 왼쪽에서 4번째 위치를 0으로 바꾼 "01001000"으로 만들어줘야한다.

 

그것은 result[i >> 3] = "01011000"와 ~(1 << (i & 7)) = "11101111"의 &연산으로 이루어진다.

 

"01011000"과 "11101111"의 &연산은 1과 &연산을 한 비트는 모두 그대로 가지고오고,

 

0과 &연산을 한다면 해당 비트는 무조건 0으로 하므로..

 

"01001000"으로 바뀐다.

 

----------------------------------------------------------------------------------------------------------

 

4-5) 소수인지 판별하는 방법..

 

소수인지 판별하는 방법은 소수가 아닐때 체에 표시하는 방법 반대로 하면 될것이다.

 

result[i >> 3]과 i의 비트 위치를 나타내는 1 << (i & 7)의 &연산이 0이 아니라면... i는 소수이다.

 

즉 result[i >> 3] & (1 << (i & 7))이 0이 아니라면 i는 소수이다.

 

구체적으로 생각해보면..

 

result[i >> 3] = "11101100"

 

(1 << (i & 7)) = "00010000"이라면?

 

result[i >> 3] & (1 << (i & 7)) = "00000000"으로 0이니까 i는 소수가 아니다.

 

그러면 (1 << (i & 7)) = "00100000"이라면?

 

result[i >> 3] & (1 << (i & 7)) = "00100000"이므로 0이 아니라 i는 소수이다.

 

 

5. 구현 예시

 

위 알고리즘을 적용해서, 에라토스테네스의 체에 그대로 적용하면 된다

 

n = int(input())

#255를 원소로 가지는 n/8 크기의 체로 초기화
result = [255]*((n+1)//8+1)

for i in range(2,int((n+1)**(1/2))+1):
    
    if result[i >> 3] & (1 << (i & 7)): #i가 소수라면..
        
        for j in range(i*i, n+1,i):
            
            #i의 배수를 모두 소수가 아니라고 표시한다
            result[j >> 3] &= ~(1 << (j & 7))
    
prime_list = [i for i in range(2,n+1) if result[i >> 3]&(1<<(i&7))]

print(prime_list)
[2,3,5,7]

 

 

에라토스테네스의 체 Bitmask로 구현하기 - Parkito's on the way (shoark7.github.io)

에라토스테네스의 체 Bitmask로 구현하기

 

[종만북] 에라토스테네스의 체를 비트마스크로 구현 방법 (tistory.com)

[종만북] 에라토스테네스의 체를 비트마스크로 구현 방법