[종만북] 에라토스테네스의 체를 비트마스크로 구현 방법
2020.03.30
에라토스테네스의 체는 굉장히 빠르게 동작하는 소수 찾기 알고리즘입니다. 알고리즘에 대해 간단히 요약을 하자면 소수를 구할 때 소수가 아닌 수들의 배수는 소수가 아니기 때문에 그들을 모두 지워나가면서 남은 수(소수) 들을 찾는 방법인데, 수의 범위가 점점 커지면, 메모리 공간이 부족하기 때문에 이를 극복하기 위해 비트 마스크를 이용합니다. (기존 알고리즘 또한 웬만한 범위 내에서는 잘 작동합니다) 따라서 비트마스크를 사용하는 구간도 메모리 영역에 국한되는데, 기존 에라토스테네스의 체 구현 과정에서 bool 배열로 범위 내 소수가 아닌 수들의 인덱스를 모두 false 처리하고, 소수들을 true 처리해서 소수들을 골라냈다면 이번엔 비트마스크를 이용해서, check 역할을 하는 배열을 unsigned char..