[백준] 1978번 소수찾기 😁 / 비트마스킹 / Python 문제풀이

풀이)

 

에라토스테네스의 체 방식을 이용하여 소수 갯수를 출력해주면 됩니다!

 

에라토스테네스의 체를 이용해 소수를 구분해주는 과정에서

일반적인 방법으로 하려면, 모든 숫자에 대해 소수인지 여부 (True/False) 를 나타내주는 값이 있어야 하기 때문에

메모리가 많이 소요됩니다. 

예를들어 10000이 소수인지 아닌지를 판별하려면

 

seive[0] = FALSE

seive[1] = FALSE

seive[2] = TRUE

이런식으로 에라토스 테네스는 길이가 10000 짜리인 리스트가 생깁니다. 

 

따라서 메모리를 줄일 수 있는 비트마스킹 기법을 사용하였습니다.

 

0 : 합성수

1 : 소수

 

seive[0] = 10101100       (순서대로 7,6,5,4,3,2,1,0에 해당하는 소수 여부)

seive[1] = 00101000       (순서대로 15,14,13,12,11,10,9,8에 해당하는 소수 여부)

 

이런식으로 비트마스킹을 통해 구성한다면 리스트의 크기를 8배 줄일 수 있습니다. 

 

---

 

해답)

import math

import functools


def findPrime(nums):
    MAX_N = max(nums)
    seive = [(1 << 8)-1] * ((MAX_N + 7)//8 + 1)

    def isPrime(k):
        return (seive[k >> 3] & (1 << (k & 7))) != 0

    def setComposite(k):
        seive[k >> 3] &= ~(1 << (k & 7))

    n = int(math.sqrt(MAX_N))
    setComposite(0)
    setComposite(1)
    for i in range(2, n+1):
        if isPrime(i):
            for j in range(i*i, MAX_N+1, i):
                setComposite(i)

    # print(functools.reduce(lambda x, y: isPrime(x) + y, nums, 0))
    res = list(filter(isPrime, nums))
    return len(res)


int(input())
inputs = list(map(int, input().split()))

print(findPrime(inputs))

 

---

함수설명)

1<<8  - 1  은 1을 비트연산으로 8번 왼쪽으로 한것을 1로 빼준 수입니다. (2의 8승 -1)

즉, 11111111 을 의미합니다.

 

def isPrime(k):

- k>>3 은 k를 8로 나눈 결과와 같습니다!

- k & 7 은 k를 8로 나눈 나머지와 같습니다!

- 따라서, seive 리스트는 8개 숫자 값씩을 갖고 있기 때문에 k >> 3 으로 참조하고, k & 7 과의  & 연산을 통해 해당 부분의 소수여부를 확인해줍니다.

 

def setComposite(k) : 

- 숫자 k 가 합성수임을 list에다 표시해줍니다.

- isPrime의 방식과 유사합니다.

 

for 문을 통해 소수인 숫자의 배수 들을 setComposite 함수를 통해 체(seive)에 표시해줍니다.